题目描述 - LC 题 15
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = []
输出：[]
示例 3：
输入：nums = [0]
输出：[]
题解
解题思路：排序+双指针
我们很容易想到的方法是三重循环，找到所有a+b+c=0的三元组，但这样的到的结果可能会有重复的。
取个简单的例子数组中的所有元素都为0，即[0,0,0,0,...,0],
如果我们直接使用三重循环枚举三元组，会得到O(N^3) 个满足题目要求的三元组（其中N是数组的长度）时间复杂度至少为O(N^3)，在这之后我们还需要利用哈希表去重，得到不包含重复三元组的最终答案，又消耗了大量的空间。这个做法的时间复杂度和空间复杂度都很高
那我们换个思路，「不重复」的本质是什么？我们保持三重循环的大框架不变，只需要保证：
- 第二重循环枚举到的元素不小于当前第一重循环枚举到的元素；
- 第三重循环枚举到的元素不小于当前第二重循环枚举到的元素。
也就是说，我们枚举的三元组(a,b,c) 满足a<=b<=c,保证了只有(a,b,c)这个顺序会被枚举到，而(b,a,c)、(b,c,a)、(c,a,b)、(c,b,a)等等这些不会被枚举。
这样就减少了重复。要实现这一点，我们可以将数组中的元素从小到大进行排序，随后使用普通的三重循环就可以满足上面的要求
同时，对于每一重循环而言，相邻两次枚举的元素不能相同，否则也会造成重复。
举个例子，如果排完序的数组为[-5,-1, -1,-2, 1, 3, 3]
第一重循环下表i为1时(nums[i]=-1,i=1)，第二重循环下表j为3时(nums[j]=-2,j=3)，第三重循环k为5时(nums[k]=3,k=5),此时枚举到第一个三元组(-1,-2,3)。
如果第三重循环继续枚举下一个元素,k为6(nums[k]=3,k=6),那么枚举到的三元组仍然是(-1,-2,3)。重复了。
继续循环，第一重循环到i为2时(nums[i]=-1,i=2)，nums[2] 也是-1，第二重循环j为3，第三重循环k为5或6时，也会枚举到三元组(-1,-2,3)，重复了。
因而我们需要在枚举到相同元素时，跳出循环，以避免重复，即nums[i] == nums[i-1] 时，跳出循环
// OC 代码如下
+ (NSArray *)threeSum1:(NSArray *)nums {
NSMutableArray *resArraym = [[NSMutableArray alloc] init];
NSArray *sortnums = [nums sortedArrayUsingSelector:@selector(compare:)];
// 枚举a
for (int i=0; i<sortnums.count; i++) {
// 需要和上一次枚举的数不相同
if (i>0 && [sortnums[i] intValue] == [sortnums[i-1] intValue]) {
continue;
}
// 枚举b
for (int j=i+1; j<sortnums.count; j++) {
if (j>i+1 && [sortnums[j] intValue] == [sortnums[j-1] intValue]) {
continue;
}
// 枚举c
for (int k=j+1; k<sortnums.count; k++) {
if (k>j+1 && [sortnums[k] intValue] == [sortnums[k-1] intValue]) {
continue;
}
if ([sortnums[i] intValue] + [sortnums[j] intValue] + [sortnums[k] intValue] == 0) {
[resArraym addObject:@[sortnums[i],sortnums[j],sortnums[k]]];
}
}
}
}
return resArraym;
}
// Swift
static public func threeSum1(_ nums:[Int]) -> [[Int]] {
var resNums = [[Int]]()
let sortNums = nums.sorted()
for i in 0..<sortNums.count {
if i>0 && sortNums[i] == sortNums[i-1] {
continue
}
for j in (i+1)..<sortNums.count {
if j>i+1 && sortNums[j] == sortNums[j-1] {
continue
}
for k in (j+1)..<sortNums.count {
if k>j+1 && sortNums[k] == sortNums[k-1] {
continue
}
if sortNums[i] + sortNums[j] + sortNums[k] == 0 {
resNums.append([sortNums[i],sortNums[j],sortNums[k]])
}
}
}
}
return resNums
}
继续
上述方法的时间复杂度仍然为O(N^3),毕竟我们还是没有跳出三重循环的大框架。
然而它是很容易继续优化的，可以发现，如果我们固定了前两重循环枚举到的元素a和b,那么只有唯一的c，满足a+b+c=0,当第二重循环往后枚举一个元素b1时，由于b1>b，如果存在c1满座a+b1+c1=0,那么c1<c,即c1一定在c的左侧。
也就是说，我们可以从小到大枚举b，同时从大到小枚举c，即第二重循环和第三重循环实际上是并列的关系
有了这样的发现，我们就可以保持第二重循环不变，而将第三重循环变成一个从数组最右端开始向左移动的指针
从而得到下面的伪代码：
nums.sort()
for first = 0 .. n-1
if first == 0 or nums[first] != nums[first-1] then
// 第三重循环对应的指针
third = n-1
for second = first+1 .. n-1
if second == first+1 or nums[second] != nums[second-1] then
// 向左移动指针，直到 a+b+c 不大于 0
while nums[first]+nums[second]+nums[third] > 0
third = third-1
// 判断是否有 a+b+c==0
check(first, second, third)
这个方法就是我们常说的「双指针」，当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法，将枚举的时间复杂度从O(N^2) 减少至O(N) 。
为什么是O(N)呢？这是因为在枚举的过程每一步中，「左指针」会向右移动一个位置（也就是题目中的b），
而「右指针」会向左移动若干个位置，这个与数组的元素有关，但我们知道它一共会移动的位置数为O(N) ，均摊下来，每次也向左移动一个位置，因此时间复杂度为O(N)
注意到我们的伪代码中还有第一重循环，时间复杂度为O(N) ，因此枚举的总时间复杂度为O(N^2) 。由于排序的时间复杂度为O(NlogN) ，在渐进意义下小于前者，因此算法的总时间复杂度为O(N^2)
上述的伪代码中还有一些细节需要补充，例如我们需要保持左指针一直在右指针的左侧（即满足b≤c），具体可以参考下面的代码，均给出了详细的注释
// OC 代码如下
+ (NSArray *)threeSum2:(NSArray *)nums {
NSMutableArray *resArraym = [[NSMutableArray alloc] init];
NSArray *sortnums = [nums sortedArrayUsingSelector:@selector(compare:)];
// 枚举a
for (int first=0; first<sortnums.count; first++) {
// 需要和上一次枚举的数不相同
if (first>0 && [sortnums[first] intValue] == [sortnums[first-1] intValue]) {
continue;
}
// c 对应的指针初始指向数组的最右端
int third = (int)sortnums.count-1;
int target = - [sortnums[first] intValue];
// 枚举b
for (int second = first+1; second<sortnums.count; second++) {
// 需要和上一次枚举的数不相同
if (second > first+1 && [sortnums[second] intValue] == [sortnums[second-1] intValue]) {
continue;
}
// 需要保证 b 的指针在 c 的指针的左侧
while (second<third && [sortnums[third] intValue] + [sortnums[second] intValue] > target) {
// third 指针左移
third --;
}
// 如果指针重合，随着 b 后续的增加
// 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
if (second == third) {
break;
}
if ([sortnums[second] intValue] + [sortnums[third] intValue] == target) {
[resArraym addObject:@[sortnums[first],sortnums[second],sortnums[third]]];
}
}
}
return resArraym;
}
// Swift
static public func threeSum2(_ nums:[Int]) -> [[Int]] {
var resNums = [[Int]]()
let sortNums = nums.sorted()
// 枚举a
for i in 0..<sortNums.count {
// 需要和上一次枚举的数不相同
if i>0 && sortNums[i] == sortNums[i-1] {
continue
}
let target = -sortNums[i]
// c 对应的指针初始指向数组的最右端
var k = sortNums.count-1
// 枚举b
for j in (i+1)..<sortNums.count {
if j>i+1 && sortNums[j] == sortNums[j-1] {
continue
}
// 需要保证 b 的指针在 c 的指针的左侧
while(j<k && sortNums[j]+sortNums[k]>target){
// k 指针左移
k -= 1
}
// 如果指针重合，随着 b 后续的增加
// 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
if j==k {
break
}
if (sortNums[j] + sortNums[k] == target) {
resNums.append([sortNums[i],sortNums[j],sortNums[k]])
}
}
}
return resNums
}
参考: https://leetcode-cn.com/problems/3sum/solution/san-shu-zhi-he-by-leetcode-solution/
