动画：一道 K Sum 面试题引发的血案

每当我遇到一个难道，脑子里下意识出现的第一个想法就是干掉它。将复杂问题简单化，简单到不能再简单的地步，也是我文章一直追求的一点。

K Sum 求和问题这种题型套娃题，备受面试官喜爱，通过层层拷问，来考察你对事物的观察能力和解决能力，这似乎成为了每个面试官的习惯和套路。打败对手，首先要了解你的对手。

看似复杂的东西，背后其实就是简单的原理和机制，宇宙万物存在的事物亦是如此。深入复杂问题内部，去看它简单的运行逻辑。将繁杂嵌套事物转化为可用简单动画表现的事物。这是一个由繁变简的过程，简单，简而不单，又单而不简。

诱饵：2Sum 两数之和

捕鱼，先要学会布网，看似一个简单题目，其实作为诱饵，引申出背后的终极 Boss。

抛出诱饵：

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

示例：给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]

大脑最先下意识想到的是，遍历所有数据，找出满足条件的这两个值，俗称暴力破解法。

解法一：暴力破解法

让目标值减去其中一个值，拿着差去数组中查找匹配是否存在，如果存在则返回下标。

/** * 解法一:暴力破解 * @param {number[]} nums * @param {number} target * @return {number[]} */var twoSum = function(nums, target) {  // 判断数组为空的情况  if (nums == null || nums.length == 1) {    return [];  }  for (let i = 0; i < nums.length; i++) {    let item = nums[i];    if (nums.indexOf(target - item, i + 1) !== -1) {      return [i, nums.indexOf(target - item, i + 1)];    }  }  return [];};

最坏的情况，需要两层 for 循环遍历所有情况。时间复杂度为 O(n²)。在这个过程中，只需要常量大小的额外内存空间，空间复杂度为 O(1)。

上述解法，耗费时间太多，但是宇宙万物任何存在对立的两种事物都是可以互相转化，时间和空间也是如此。

解法二：哈希表

因为我们在遍历的时候，用 target 取数据的时候，需要再遍历一遍数组，这才导致了耗费时间过长。我们把这部分时间转化为空间，用空间换时间，能将空间换时间的非哈希表莫属。

数组本来就存在映射，通过下标取出对应值，但是我们这次是通过 target 值减去其中一个值，得到另一个值，通过这个值得出下标确不能。

所以需要让数组的值和下标索引做一层映射，如果已知值，可以通过哈希映射得到下标索引 index。

/** * 解法二:两遍哈希表法 * @param {number[]} nums * @param {number} target * @return {number[]} */var twoSum2 = function(nums, target) {  // 将值存储到哈希表中  let map = new Map();  // 存储  nums.forEach((item,index) => {    map.set(item, index);  });  // 判断  for (let i = 0; i < nums.length; i++) {    let item = nums[i];    console.log(map.get(target - item))    if (map.has(target - item) &&  map.get(target - item) !== i) {      return [i, map.get(target - item)];    }  }  return [];};

借助哈希表，空间换时间，时间效率降低了一个维度，时间复杂度为 O(n)。空间需要 n 大小的额外内存空间开辟哈希表的空间大小，空间复杂度为 O(n)。

解法三：哈希表优化

对于以上哈希表，我们需要一遍先去存储值和索引的映射，如果我们在遍历查找的时候存储，不是可以节省这个步骤吗？

如果我们查找目标值的时候，在哈希表中查找，如果能够找到，就返回该值的下标，如果找不到，则将改值的映射加入到哈希表中，这样一边就完成查找数据和添加数据。

/** * 解法三:哈希表法优化 * @param {number[]} nums * @param {number} target * @return {number[]} */var twoSum3 = function(nums, target) {  // 将值存储到哈希表中  let map = new Map();  // 存储  for (let i = 0; i < nums.length; i++) {    let item = nums[i];    if (map.has(target - item) && map.get(target - item) !== i) {      return [map.get(target - item), i];    }    map.set(item, i);  }  return [];};

上钩：3Sum 三数之和

此时，我们的解答和优化受到面试官的表扬，你认为这完美的解题思路可以拿到 offer 的时候，但却这只是个热身，因为你已经上钩了。

上钩诱导：

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

例如：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组集合为：[  [-1, 0, 1],  [-1, -1, 2]]

这次从两个数升级到了三个数，此时你心里的感受是既高兴又担心。我们有了上一题的解题优化思路，你想着这道题会不会是同样的思路呢？

暴力破解三层 for 循环固然能解，但是肯定耗费时间比 n² 还要长，所以你想着用哈希表做优化。

1、解法一：哈希表

先用两层 for 循环，固定两个数，然后在用哈希表去找第三个数，直到找到为止。

/** * 解法一：哈希表优化 * @param {number[]} nums * @return {number[][]} */var threeSum = function(nums) {  var res = [];  var map = new Map();  for (let i = 0; i < nums.length - 2; i++) {    for (let j = i + 1; j < nums.length - 1; j++) {      let item = 0 - nums[i] - nums[j];      if (map.has(item)) {        res.push([item, nums[i], nums[j]]);      } else {        map.set(item, 1);      }    }  }  return res;};

但是这次，并不是空间换时间，因为两层 for 循环，导致了时间复杂度为 O(n²)，而且空间上需要额外大小为 n 的内存空间存储哈希表，不仅时间效率还是空间效率，都是不乐观的。

此时的你，陷入了深思...

2、解法二：排序 + 双指针

以往的面试者到这里基本被淘汰掉了，剩下的为有经验的应聘者，他会根据以往的做题经验总结的来优化本题。

如果我先固定一个数，另外两个数我要懂得变通，如果三者和小于目标值，我再让另外两个数其中之一换一个大点的。如果三者之和大于目标值，我就让两个数其中一个换一个小点的。

对于换个大点的或者小的数据，一个数据要有阶梯的层次，就必须进行排序，排序最好的时间复杂度为 O(nlogn)。

我们用两个指针，分别指向最大值和最小值，固定其中一个数，让这个固定的数和其余两个指针指向的数三者相加，如果小于目标值，就让指向最小值的数右移，变的大一些，否则，指向最大值的指针左移，指向的数稍微小一些。

/** * 解法二：排序 + 双指针(去重) * @param {number[]} nums * @return {number[][]} */var threeSum = function(nums) {  var res = [];  var len = nums.length;  // 判断特殊情况  if (nums == null || len < 3) return res;  nums.sort((a, b) => a - b); // 从小到大排序  for (let i = 0; i < len; i++) {    // 如果固定的数为正整数,不可能存在为 0 情况    if (nums[i] > 0) break;    // 去重(如果下一个固定数和前一个相等,后边会出现重复结果)    if (i > 0 && nums[i] == nums[i - 1]) continue;    // 定义左右指针    let L = i + 1;    let R = len - 1;    while (L < R) {      // 结束遍历条件      let sum = nums[i] + nums[L] + nums[R];      if (sum == 0) {        // 去重        res.push([nums[i], nums[L], nums[R]]);        while (L < R && nums[L] == nums[L + 1]) L++;        while (L < R && nums[R] == nums[R - 1]) R--;        L++;        R--;      } else if (sum < 0) {        L++;      } else if (sum > 0) {        R--;      }    }    return res;  }};

如果你实践了，发现之前的解法也是行不通的，为啥？因为没有去重，比如[-1,0,1,-1]。其中[-1, 0, 1]、[0, 1, -1]结果都会让值等于目标值 0，但是这两个结果重复了。

要想做到去重，我们就要找到去重的规律。我分为以下几个点：

num[i] > 0 时，无论左右指针如何移动，找不到任何满足条件的值。

// 如果固定的数为正整数,不可能存在为 0 情况if (nums[i] > 0) break;

num[i] = num[i - 1] 当前值和前一个值重复，寻找的值也会重复，所有跳过。

// 去重(如果下一个固定数和前一个相等,后边会出现重复结果)if (i > 0 && nums[i] == nums[i - 1]) continue;

sum = 0 时，左右指针移动也会存在重复的值。

nums[L] = nums[L + 1],让 L++ 继续寻找下一个匹配的值。

 while (L < R && nums[L] == nums[L + 1]) L++;

nums[R] = nums[R - 1],让 R-- 继续寻找下一个匹配的值。

和以上同理！

while (L < R && nums[R] == nums[R - 1]) R--;

通过上边对各个查重边界条件的判断，最后的结果不会有重复数据了。

在空间上，不需要空间大小为 n 的内存空间，空间复杂度降到 O(1)。

你以为完事了，其实还没有，这才到了中期，也是在有经验的应聘者中筛选，面试官想要在最后的应聘者中再进行筛选，肯定还要进一步考察你对本题的思考。

再来：4 Sum 四数求和

三数之和求解巧妙的排序设计和双指针的运用，已经让我们对齐有些心有余力而力不足。

继续升级到 4 Sum 四数求和问题，如果有了以上的思路，4 Sum 求和难不到你，运用同样的思路，先固定两个数，然后还是运用双指针求另外两个满足条件的数字。

/** * @param {number[]} nums * @param {number} target * @return {number[][]} */var fourSum = function(nums, target) {  var res = [];  var len = nums.length;  if (nums == null || len < 4) return res;  nums.sort((a, b) => a - b);  for (let i = 0; i < len - 3; i++) {    // 去重(如果下一个固定数和前一个相等,后边会出现重复结果)    if (i > 0 && nums[i] == nums[i - 1]) continue;    //计算当前的最小值，如果最小值都比target大，不用再继续计算了    if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;    //计算当前最大值，如果最大值都比target小，不用再继续计算了    if (nums[i] + nums[len - 1] + nums[len - 2] + nums[len - 3] < target)      continue;    // 确定第二个指针的位置    for (let j = i + 1; j < len - 2; j++) {      // 去重      if (j > i + 1 && nums[j] == nums[j - 1]) continue;      // 定义第三/四个指针      let L = j + 1;      let R = len - 1;      //计算当前的最小值，如果最小值都比target大，不用再继续计算了      let min = nums[i] + nums[j] + nums[L] + nums[L + 1];      if (min > target) continue;      //计算当前最大值，如果最大值都比target小，不用再继续计算了      let max = nums[i] + nums[j] + nums[R] + nums[R - 1];      if (max < target) continue;      while (L < R) {        let sum = nums[i] + nums[j] + nums[L] + nums[R];        if (sum == target) {          res.push([nums[i], nums[j], nums[L], nums[R]]);        }        if (sum < target) {          while (nums[L] === nums[++L]);        } else {          while (nums[R] === nums[--R]);        }      }    }  }  return res;};

同样，对于 4 sum 四数求和的性能，借助排序 + 双指针方法并没有使得效率和空间变坏，所以同样适用。

但是唯一不同的就是一些特殊的边界条件变化，比如：

//计算当前的最小值，如果最小值都比target大，不用再继续计算了if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;//计算当前最大值，如果最大值都比target小，不用再继续计算了if (nums[i] + nums[len - 1] + nums[len - 2] + nums[len - 3] < target)

Boss：K Sum K 数求和

从 2Sum，上升到 3Sum，然后到了 4Sum，最后可以归结为 KSum 问题。

解题的关键不仅仅是利用排序和双指针问题，而且对于几个特殊情况的优化，对整体d代码的执行效率也有很大关系。

在 4Sum 求和中，我尝试着增加了对几个特殊情况判断，如：

//计算当前的最小值，如果最小值都比target大，不用再继续计算了let min = nums[i] + nums[j] + nums[L] + nums[L + 1];if (min > target) continue;//计算当前最大值，如果最大值都比target小，不用再继续计算了let max = nums[i] + nums[j] + nums[R] + nums[R - 1];if (max < target) continue;

针对特殊情况优化的执行结果对比如下：

小结

通过对这个面试题深入的分析和总结，收获很多，不仅是对本题的收获，更多的是对所有算法题的一个概括。

鹿哥，你这不只是分析了一个算法题吗？你咋就对其他题目也有收获呢？

题不在于刷多，刷更多的题是为了熟悉更多的题型和练习自己对题目的敏感度或者可以说总结出算法题的一些套路。

这个题它本身就可以所有算法题从繁杂到简化的一个过程，跑不出空间与时间的转化，也跑不出对一些边界条件的思考，以后无论做什么算法题，都跑不出这两样东西。

我们虽然看它表面在变化，但是它的实质并没有变化，任何事物都由最简单的事物构成，所谓的复杂，只是你把它想象的过于复杂。

更多相关文章

随机推荐