[数据结构与算法]2021-09-05 Leetcode 15. 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一:

暴力求解,3重循环.
时间复杂度:O(n^3)
这个解法超过了Leetcode的运行时间限制.无法提交.

解法二,双指针法:

先对nums排序(升序).平均时间复杂度O(n*log(n))

为了方便,我把a数字与a数字的数组下标混在一起说了.以下所有说到右移++、左移–,都指的是数组下标的操作.

设定a<b<c,第一重循环遍历a.
关键在第二重循环.b从a+1开始,自左向右递增.c从最右侧开始,自右向左递减.

1. 如果a+b+c==0,找到结果.则b++.由于b右移变大了,为了满足a+b+c=0,于是c–.
2. 如果a+b+c>0并且b<c,则c–.这个好理解.
3. 如果b==c,则说明a+b+(b+1)>0.此时b右移没有意义,因为a+(b+1)+(b+2)也必然大于0. 因此要跳到第一重循环a++.
4. 如果a+b+c<0,结合条件1、2,隐含说明a+b+(c+1)>0.此时b右移没有意义,因为a+(b+1)+(c+1)也必然大于0.因此要跳到第一重循环a++.

综上,第二重循环可以概括为如下伪代码:

 while(b<c && a+b+c>0)
 	c--;
 if(b==c) //由于上面的if先判断b<c,因此这里要先过滤b==c的情况.不能与下边的if调换顺序
 	break;
 if(a+b+c==0)
 	存结果;
 	c--;
 	continue;
 else //a+b+c<0
 	break;

可以发现,b与c,一个向右,一个向左,直到两者相遇.它们的移动没有嵌套的循环关系.因此第二层循环的时间复杂度就是O(n).
再考虑第一层循环的嵌套关系,整体时间复杂度是O(n^2)