15、三数之和
一、思路
1、本人思路
采用了两数之和的思路：
使用一层嵌套for循环和一个哈希表。
伪代码：
1、从第一个数开始作为for循环的第一层i=0；
2、嵌套for循环使用第二个数为开始：i+1；
3、判断哈希表中是否存在值： 0-nums[i]-nums[i+1] 。若存在则将三个数存入数组；若不存在则将将继续循环；
代码实现有待商榷
2、官方思路
与两数之和类似；
排序+双指针
官方解的思路由标准解到优化解，一步一步分析，由浅入深，实在享受！
- 标准解：题目中规定不可以返回重复的元组，当使用三重循环的暴力解时，很容易出现重复解的情况，最后还需要使用集合来去重，时间和空间复杂度都很大。
- 第一次优化。仍然在三重循环的框架下，优化重复情况。那么就要保证，在第二次循环时的元素不小于第一次循环的元素；第三次不小于第二次。所以可以对数组进行一次排序。即a<=b<=c,得出元组(a,b,c)，那么就不会有(b,a,c)这种情况。
- 但是排序后，可能会有相邻元素是一样的情况，那么也会造成重复。那么我们就要在第一次循环完成后跳到下一个数而不是下一位数，第二第三次相同。（代码实现就是加一个判断）到此时完成了第一次优化，但是在三重循环框架下，复杂度仍为O(n*3)
- 第二次优化，双指针的出现。我们根据数学知识可以发现，确定a、b后，c一定是唯一的。那么在第二次循环时，在b之后循环一位b1，b1>b。那么c1一定小于c：a+b1+c1=0，也即c1一定在c的左侧。所以我们在第二次循环时，b从左向右遍历时，c可以从右向左遍历。**第二和第三重循环就变成了并列关系！**非常的巧妙！