首页 > 代码库 > leetcode -- 3 sum

leetcode -- 3 sum

3-sum 

  题目描述:

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

题目要求:

  • 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.

每个三元组内的元素是按非递减的顺序存放的,并且结果中要求不含有相同的集合。

解法:首先是排序,接着要求是不含有相同的集合,显然可以使用set,但是下面的代码全部都避免使用set


下面一共使用了3种方法:

法一:DFS,复杂度高,并且在很小的例子上都超时。

<script src="https://code.csdn.net/snippets/372238.js" type="text/javascript"></script>

法二:枚举所有的2-sum和。再在数组中查找是否存在另外一个数,使得该3个数的和为0.

此法不需要使用set,直接就可以得到结果,但是要注意避免重复计算,如下两点。


注1:上述的枚举2-sum时,对于剩下的那个数只需要在 “下标都大于前两者时”进行。如下例:


在上图中,当枚举到i和j时,另外一个元素只需要在  图示的 k  范围内枚举即可。

注2:如果数组中有大量的重复元素,那么i和j(保持有A[i] == A[j])就只需要考虑一次即可。

如下例:


上图中,i 和 j只需要考虑一次, 当 j 移动到 j‘ 的时候,是不需要考虑的,因为与前面的 i 和 j  是重复的。

代码如下:

<script src="https://code.csdn.net/snippets/372251.js" type="text/javascript"></script>

时间复杂度为: n^2(logn)

法三:由于2-sum在数组有序的情况下我们是可以O(n)的时间来解决的,于是直接使用已有的2-sum的代码,代码如下:
<script src="https://code.csdn.net/snippets/372269.js" type="text/javascript"></script>