SUM系列，下篇

声音

题目

3 Sum

https://leetcode.com/problems/3sum/description/

4 Sum

https://leetcode.com/problems/4sum/description/

3 Sum Closest 寻找最接近的结果

https://leetcode.com/problems/3sum-closest/description/

讲解

在 Sum 的上篇，我们解决了前三道题。 Two Sum, Two Sum II, Two Sum III. Two Sum IV 是变形成树状结构。我们这里就不展开讲了，或许会留到跟二叉树有关的文章里面讲述下。

现在，我们就来介绍下后面的三道题：

先说 3 Sum,

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:

[

[-1, 0, 1],

[-1, -1, 2]

]

简单的说，我们可以把 3Sum这道题，变形成一道2Sum的题。还记得我们上篇文章解决2Sum的两种方法么？方法1，是先建立一个哈希表，然后查找；方法2 ，是先把数组排序，然后从两头向中间查找。 现在要解决三个数相加的问题，我比较倾向于采用方法2，因为我们要先固定一个数，才能把这道题转化为2Sum.先固定最小的数，这样比较容易理解，也比较容易处理重复答案。

这道题里面最麻烦的就是要处理，重复的数据。假设这道题的输入数据是。我们怎么才能保证，输出的数组只有一个［0，0，0］呢？

我在下文的代码中加了两个很重要的判断（已加黑）。假设我们的数据是｛1，2，3，4｝。 通过 第一轮计算我们容易得到结果是［1，2，4］，我们固定的是第一个1，那么在继续通过2，3去匹配查找时，2和3的查找性质是完全一样的，所以要跳过。同理，当我们固定2的时候，2与1的值一样，也是需要跳过的。因为我们前面已经比较过一个相同值的数字了。所以不应该在比较第二次。

还要注意，在这里判断重复数字的时候，不要把［1，2，3］，也忽略掉。所以，我们故意加了一个判断条件，begin-i > 1,以避免正确的结果被跳过。这里不比较1与2的深层含义，是因为2相当于求新一轮b+c=0的开始，这里1相当于固定的a，2相当于新一轮的b。

4SUM 与 3Sum，类似， 这里面最重要的测试数据就是 。 而上文提到的关于重复数据的监测，也有三处。大家写代码的时候，一定要注意。

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:

[

[-1, 0, 0, 1],

[-2, -1, 1, 2],

[-2, 0, 0, 2]

]

最后我们再来介绍下， 3Sum Closest,

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

这道题如果也采用先排序的方法解决，那么最重要的是，比较的时候，采用什么的方式进位，以及如何获得最近的距离。

很显然，最近的距离 ＝ abs(target － num1 - num2 -num3). 如果我们发现最近的距离，比之前存储的小，就可以把他存下来。

如果迫近两边的值，去得到目标值，就比较简单了。我们把 temp = target - num1 -num2 - num3. 和之前一样， temp 大于0，移动最小值。Temp 小于 0， 移动最大值。 答案如下：

其实 LeetCode 里面 还有很多新的 Sum类型的题，例如：

3Sum Smaller

https://leetcode.com/problems/3sum-smaller/description/

4Sum II

https://leetcode.com/problems/4sum-ii/description/

大家有兴趣也可以自己做一下。如果实在没有思路，或者没有付费所以看不到。也可以给公众号留言，我们可以再更一篇， Sum附加篇。

封面图来源：猥琐流摄影大师蹲点偷拍邪魅狂狷美猫出浴图（重金购置，版权所有，转载请保留水印和前述20字的作品名）

（亲，领一个呗~亲~~）