613，双指针解三数之和
问题描述
来源：LeetCode第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]]
示例 3：
输入：nums = []
输出：[]
示例 3：
输入：nums = [0]
输出：[]
提示：
0<=nums.length<=3000
-10^5<=nums[i]<=10^5
双指针解决
这题说的是找出3个数字的和是0，如果使用3个for循环，这样时间复杂度太高（n^3），数据稍微大一点就容易超时，所以这种实现方式不在我们考虑范围内。
我们这样来思考一下，如果数组是排序的，3个数字我们固定一个，就变成了从有序数组中选择两个数字，让他的和等于一个固定的值了。这样就可以使用双指针了。我们以示例一为例画个图看一下（先对数组排序）
在排序数组中找出两个数字的和等于一个固定的值，使用两个指针即可完成。但这里有可能会出现重复的结果，所以我们需要过滤掉重复的结果。怎么过滤，我们来思考这样一个问题，在数组
[a,a,b,c]
如果a+b+c=0，因为有两个a，那么就会出现两个a+b+c=0的结果，所以我们需要过滤掉一个，怎么过滤呢，就是当前数字如果和前面一个数字相同，我们就跳过。比如上面第2个a和第一个a相同，我们直接跳过。来看下最终代码
public List<List<Integer>> threeSum(int[] num) {
//先对数组进行排序
Arrays.sort(num);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < num.length - 2; i++) {
//过滤掉重复的
if (i > 0 && num[i] == num[i - 1])
continue;
//因为是排序的，如果第一个数字大于0，那么后面的也都
//大于0，他们三个数字的和不可能等于0
if (num[i] > 0)
break;
int left = i + 1;//左指针
int right = num.length - 1;//右指针
int target = -num[i];
while (left < right) {
//左右指针的和
int sum = num[left] + num[right];
if (sum == target) {
//找到了一组，把他们加入到集合list中
res.add(Arrays.asList(num[i], num[left], num[right]));
//过滤掉重复的
while (left < right && num[left] == num[left + 1])
left++;
while (left < right && num[right] == num[right - 1])
right--;
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
return res;
}
排序的时间复杂度是O(nlogn)，for循环中的时间复杂度是O(n)，for循环里面的时间复杂度是O(n)，他们是相乘的关系，所以他们的时间复杂度是O(n^2)，整个代码的时间复杂度就是O(nlogn)+O(n^2)，也就是O(n^2)。
截止到目前我已经写了600多道算法题了，为了方便大家阅读，我把部分算法题整理成了pdf文档，目前有1000多页，大家可以在下面公众号“数据结构和算法”中回复关键字“pdf”即可获取下载链接。