学习
实践
活动
专区
工具
TVP
写文章

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字的作品名)

(亲,领一个呗~亲~~)

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180110G01QQZ00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

关注

腾讯云开发者公众号
10元无门槛代金券
洞察腾讯核心技术
剖析业界实践案例
腾讯云开发者公众号二维码

扫码关注腾讯云开发者

领取腾讯云代金券