前端乱纪元，修习一下内功——前端算法（二）

前言

这次跟大家介绍的算法是哈希表和回溯。这两种算法在我们解算法题或者在工作中都是特别常见的。

哈希表

哈希表也叫散列表，通常是一组一组key-value形式的数据结构，是一种方便我们在用到的地方进行快速取值的数据结构。在我们前端，哈希表存在的形式可以是object，也可以是Map。

哈希表的概念倒是不难，那它到底是怎么在算法中发挥作用的呢？

举个简单的例子，大家一看便知：

梦开始的地方，力扣算法第一题：

两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

输入： nums = [2,7,11,15], target = 9
输出： [0,1]
解释： 因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

根据题意，我们最开始的思想就可能是，这还不简单，我反手搞个双循环,外层循环固定第一个数，内层循环遍历它后面的数，两数之和等于target就返回答案，美滋滋：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    for(var i = 0;i < nums.length;i++) {
        for(var j = i + 1;j < nums.length;j++) {
            if(nums[i] + nums[j] == target) {
                return [i,j]
            }
        }
    }
};

当然，对于这道简单题来说，这么做没什么问题，但是，如果我要你只写一层循环就找到答案，那要怎么来写呢？这里就引出我们今天要说的第一位主角——哈希表。

思考：

• 我们哈希表中到底要存些什么数据呢？
• 我们在什么时候去取用哈希表中的数据呢？

根据题目，我们可以看到，题目中最终想要我们返回的答案是数组下标，那么我们的哈希表就可以设计为：key就是我们数组中每一项的值，然后我们就把这个值对应的下标作为value给存储进去。

然后我们在遍历数组的时候，可以进行判断，如果target减去我们当前项所得到的数，在我们维护的哈希表中已经存在了，那么直接将当前项的下标和哈希表中维护数值的下标直接返回就是答案；如果target减去我们当前项所得到的数，并不在哈希表中，那么我们就把当前的值以及它对应的下标维护进我们的哈希表中。

var twoSum = function(nums, target) {
    var m = new Map()
    for(var i = 0;i < nums.length;i++) {
        if(m.has(target - nums[i])) {
            return [i, m.get(target - nums[i])]
        }else{
            m.set(nums[i], i)
        }
    }
};

这样，我们就可以利用哈希表，只用一层循环就找到了答案。

哈希表相对来说比较简单，但我们在什么时候用，怎么用，这就需要我们多想多练。

来看一个经典的题目吧

斐波那契数列

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

这道题根据题意，我们应该能想到的最直接的写法是这样的：

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
    if(n == 0 || n == 1) return n
    var mod = 1000000007
    return (fib(n - 1) + fib(n - 2)) % mod
};

这么写就是把题目条件给写成了算法，很简单，但是不好意思，当我们点击提交的时候是无法通过的。超出题目规定的运行时间限制。所以我们就要想办法对上面的逻辑处理进行优化：

当然这道题可以用动态规划来做，也不难，但是这里我们想讲的是哈希表，那我们来思考一下这道题要如何运用哈希表呢？

• 首先我们来想一下，我们上面那么写算法，不能通过，那它到底是输在哪里了呢？
• 我们可以发现，其实我们的算法在实际的运行过程中是存在着大量的计算的

比如：

如果我们要求F(6)，那么我们的算法执行就会是

• F(6) = F(5) + F(4) = F(4) + F(3) + F(4) //这里我们可以发现，计算F(4)我们计算了两次

这里我们n还仅仅是取了一个很小的数字6，如果这个n数字很大很大呢，999999呢，我一个函数干了半天活终于求出了F(999997)的值，还以为胜利就在前方了，结果你告诉我还要再来一遍。。。而且999997也不小了吧，我想计算它的值，那它的内部又存在大量的重复计算。

所以这里我们可以用Map来记录一下我们计算过的值，如果我们所要计算的n已经存在在我们的哈希表中了，那直接拿来用就完了，不需要再走一波函数递归调用半天来计算了。如果不存在，那我们再去计算，计算完了之后，将值存储在哈希表中，下次需要用了直接拿出来。

所以我们最终的代码就是：

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
    var mod = 1000000007
    var m = new Map()
    function getAns(num) {
        if(num == 0 || num == 1) return num
        if(m.has(num)) {
            return m.get(num)
        }else{
            let tmp = getAns(num - 1) + getAns(num - 2)
            m.set(num, tmp)
            return tmp%mod
        }
    }
    return getAns(n)
};

这次我们再次执行，不会再报超出时间限制的错误了。怎么样，有没有感受到哈希表的神奇呢？

回溯

接下来，引出今天的第二个主角——回溯

回溯算法和我们上一节提到的DFS(深度优先搜索)算法有些类似，就是从一条路往前走，能进则进，不能进，就返回回来再从另一条路走，我每条路都去试一试总能找到我要的答案。回溯的本质可以理解为就是暴力穷举的算法，去尝试所有可能的线路，可是一旦我们的返回条件设置的不合理，就会导致走很多的无用路，使得算法不高效。所以一般我们在回溯中还会涉及到剪枝的思想。

剪枝，就如同字面意思，剪去枝叶，而这里的枝叶指的当然是不必要的枝叶。换在算法中就是不必要的路径，就好像，我买了一瓶饮料，当我刮开瓶盖，看到第一个字是“谢”的时候，那后面我还需要把字刮完吗？当然是不必了。那这种把后续的流程给优化掉的操作，在算法中就叫剪枝。

来到题目我们实际看一下：

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

例子：

输入： n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

这道题，就是一道典型的需要用回溯来做的题目，我们要把所有可能的组合都放在答案数组，那当然要把所有可能的路径都要走一遍，那这种操作就跟我们想要暴力枚举的想法很契合了，所以就可以用回溯来做。

我们来理一下思路：

• 题目要求我们返回所有可能的k个数组合，那我们就必须要合理的规划我们取数的路径，保证能够覆盖所有的情况
• 对于上面的例题，我们的思路可以是这样的：

根据我们上图中的思路，我们可以编写这样一个递归函数，在这个函数中我们可以接收一个数值，这个数值是我们这次操作所取的数字，同时题目要求我们最后返回的是数组，所以，在递归函数中我们还需要维护一下，所走过路径组成的数组。

最终我们的递归函数可以设计为这样：

function getAns(val, arr) {
    arr.push(val)
    // 当我们所维护的数组长度达到K时，说明这条路径已符合题意，不用再继续遍历了
    if(arr.length == k) {
        /* 符合题意，将该数组放入最终的答案数组中 */
        return
    }
    for(var i = val + 1;i <= n;i++) {
        getAns(i, [...arr])
    }
}

我们取一个数，维护进数组，遍历所取数字后边的所有数字，递归调用自身。直到当我们这条线维护的数组长度符合题意，那么就可以推入我们的答案中。

递归函数设计好之后，那么我们整个的题目就可以做出来了：

var combine = function(n, k) {
    var ans = []
    function getAns(val, arr) {
        arr.push(val)
        if(arr.length == k) {
            ans.push(arr)
            return
        }
        for(var i = val + 1;i <= n;i++) {
            getAns(i, [...arr])
        }
    }
    for(var i = 1;i <= n;i++) {
        getAns(i, [])
    }
    return ans
};

上面就是一个典型的回溯算法的解题步骤。

问题解决了，回溯的思想也学会了，很棒。但是，对于这道题我们还有很大的优化空间，接下来我们开始对我们的路径进行剪枝。

首先我们可以想一下，题目中要求我们一定是k个数字组成的数组，所以，当我们遍历第一个数的时候就发现，后边剩余的数字根本就凑不够k个数，那当然就不需要再遍历了。所以我们可以将我们的函数修改成这样：

var combine = function(n, k) {
    var ans = []
    function getAns(val, arr) {
      ...
    }
    /* 当我们路径开始的第一个数字是n - k + 2的时候，我们后续剩余的数字
     已经不足够支撑组合一个长度为k的数组了 */
    for(var i = 1;i <= n - k + 1;i++) {
        getAns(i, [])
    }
    return ans
};

这样一来我们就少走了k - 1个路径，而且是从起点就掐断了。

上面我们只是对路径的起始点进行剪枝，同样的道理，我们还可以在递归函数的内部进行剪枝。

• 我们在递归函数中维护了整个路径组成的数组，那么我们就可以判断，这个数组如果想满足k的长度时，还需要几个数，也就是 k - arr.length 个数字。如果我们后续的数字个数比 k - arr.length 要少，那后续的路当然也不必再走了，不可能得到答案，剪掉后续的路径。

所以我们再次剪枝得到：

var combine = function(n, k) {
    var ans = []
    function getAns(val, arr) {
        arr.push(val)
        if(arr.length == k) {
            ans.push(arr)
            return
        }
        if(n - val < k - arr.length) return
        for(var i = val + 1;i <= n;i++) {
            getAns(i, [...arr])
        }
    }
    for(var i = 1;i <= n - k + 1;i++) {
        getAns(i, [])
    }
    return ans
};

这样一波剪枝操作下来，是不是明显从感觉上就觉得我们这个算法相比原来，少走了很多弯路，减轻了很多负担呢？

最后

至此我们对哈希表和回溯以及剪枝都有了一定的认识。

对于路径问题，罗列所有组合的问题，以及找子集的问题等等我们都可以尝试用回溯来去解题，但这里我们一定要灵活的运用剪枝技巧，只有剪枝逻辑条件写的好，我们的算法性能才足够高。

而哈希表的舞台可就更多了，凡是涉及到数据重复计算，需要收集某些特定下标的情况，我们都可以用到哈希表。

往期内容：

DFS,BFS：前端乱纪元，修习一下内功——前端算法

双指针与二分法：前端算法——双指针和二分法