题目:
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.
Example:
S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
分析:
最简单的方法是用一个三层循环，枚举所有可能的3个数字的组合，找出所有3个数字加起来等于0的组合。时间复杂度为O(n^3)。
很明显我们可以想出更好的办法来解决这个问题
在此我用题目中的例子来演示一下我的算法，而不作概括性的讲解
S = [-1, 0, 1, 2, -1, -4]
首先将array排序一下
sorted = [-4, -1, -1, 0, 1, 2]
假设k = -4是一个3sum组合的第一个数字
用index i指向-4 后面的数字-1
用index j指向最后1个数字2
如果k = -4是一个3sum组合的第一个数字，那么后面2个数字加起来一定要等于4
但是-1+2=1，而-1和2之间的数字加起来也不可能比1大，所以我们永远不可能从-1,-1,0,1,2这堆数字中找出sum为4的2个数字，所以，"-4是一个3sum组合的第一个数字"这个假设明显是错误的
(这个算法看起来有点像数学证明里的proof by contradiction, 这个学期经常用这个证明方法来证明算法的正确性，所以想出这个方法也算很自然哈哈)
现在，假设k = -1是一个3sum组合的第一个数字
用index i指向-1 后面的数字-1
用index j指向最后1个数字2
如果-1是一个3sum组合的第一个数字，那么后面2个数字加起来一定要等于1
很幸运，sorted[i]和sorted[j]现在指向的2个数字-1和2的sum刚好就是1，所以我们已经找到了其中一个组合: -1, -1, 2。
接下来让i自增1，指向0
让j自减1，指向1
0+1 = 1，所以我们又找到了另一个组合-1,0,1
只用这个例子的话，没有概括到算法的所有方面。
如果sorted[i]+sorted[j] < 0 - k，要如何移动i和j?
这个时候应该让i自增，指向一个更大的数字，使得sorted[i]+sorted[j]更接近0 - k
如果sorted[i]+sorted[j] > 0 - k，则应该要j自减，使得sorted[i]+sorted[j]更接近0 - k
以此类推，直到i和j重合，证明已经没有办法找到更多3Sum组合了
class Solution {
public List<List<Integer>> threeSum(int[] num) {
List<List<Integer>> lists = new ArrayList<List<Integer>>();
Arrays.sort(num);
for(int k = 0; k < num.length - 2; k++) {
int i = k + 1;
int j = num.length - 1;
int target = 0 - num[k];
while(i < j) {
if(num[i]+ num[j] == target) {
lists.add(Arrays.asList(num[k], num[i++], num[j--]));
while(i < j && num[i] == num[i - 1]) i++;
while(i < j && num[j] == num[j + 1]) j--;
}
else if(num[i]+ num[j] < target) i++;
else j--;
}
// Skip duplicates(keep skipping until num[k+1] != k), remember, the for loop will add 1 to k, so that next num[k]
// won't be a duplicate
while(k < num.length - 2 && num[k] == num[k+1])
k++;
}
return lists;
}
}
时间复杂度为O(n^2)
