LeetCode第15,16,18题:3Sum, 3Sum Closest and 4Sum总结

这三道题明显是一家子,放到一起。。。

题目一 3Sum

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:
Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
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)

  • 大意:给定一个有n个整数的数组S,数组中是否存在元素a, b, c使得a + b + c = 0? 找出所有的组合。

题目二 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).

  • 大意:给定一个有n个整数的数组S和一个给定的目标值tatget,找出数组中三个数a, b, c,使得三个数之和a + b + c最接近target,输出这个和。

题目三 4Sum

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:
Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
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)

  • 大意: 同题目一,和题目一唯一的不同是从三个数变成了四个数。

思路和题解(Python)

思路一 (3Sum)

其实,3sum这道题也是和leetcode第一题Two Sum类似的,回顾Two Sum这道题,发现,可以利用哈希的思想,创建一个数组/map(python就可以是dict)把O( n^3 )的复杂度降为( n^4 )。

这里把这种方法用dict实现,具体思路是:
1. 先遍历所给数组,以数为key,数出现的次数为value,创建一个dict;
2. 然后两层循环选定前两个数a, b(O( n^2 )),进行常数查找(0 – a – b)是否存在字典中,若存在,则将这个三元组添加到待返回的list变量ret中。

需要注意两点:
1. 注意选定前两个数时,暂时将对应的count值-1;
2. 注意将符合条件的组合添加到ret前,检查ret中是否存在有重复的组合。

代码如下:

思路二 (3Sum, 3Sum Closest and 4Sum)

但是,当我再想用这种思路解决问题二(3Sum Closest)时,就会发现目标并不是一个定值,所以查表确定是否符合条件的思路就行不通了,因为这道题是让我们解决最优的问题,而不是确切数值的问题。

所以经过百度发现,其实这类问题还可以个用另一种方法,步骤如下:
1. 将所给数组排序
2. 定义两个指向最小数和最大数的”游标“,两边移动”游标“向里逼近,逐步找到目标值

由于这种遍历将两个”游标”,放到一趟进行,向中间逼近,所以会将复杂度降为O( n^2 )

这种思路需要注意的是:
因为没有了上一思路的dict或者map来记录数字出现的次数,所以消除可能出现重复组合需要用到一个消除相同值(remove duplicates)的循环的技巧,详见代码。

用这种思路解决问题一(3Sum)的代码如下:

对于问题二(3Sum Closet),答题思路是相同的我们只需适当修改上题的代码,在每层循环外更新一个最小相差值(这里分别为closetsub_closet),并适当优化(比如当相差0时,可以直接return)

用这种思路解决问题二(3Sum Closet)的代码如下:

对于问题三(4Sum),不管我们通过上述哪种思路,都只能再在原来复杂度的基础上*n,即复杂度为O( n^3 ),这里的代码,还是用游标指针向中间逼近的方法,只要在3Sum的代码加一层循环,就可以得到本题的代码:

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注