学习笔记--算法（双指针）7
三数之和
链接：
. - 力扣（LeetCode）
题目描述
给你⼀个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满⾜ i != j、i != k 且 j != k ，同时还满⾜ nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
⽰例 1：
输⼊：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
⽰例 2：
输⼊：nums = [0,1,1]
输出：[]
解释：
唯⼀可能的三元组和不为 0 。
⽰例 3：
输⼊：nums = [0,0,0]
输出：[[0,0,0]]
解释：
唯⼀可能的三元组和为 0 。
提⽰：
3 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5
解法（排序+双指针）
算法思路
本题与两数之和类似，是⾮常经典的⾯试题。
与两数之和稍微不同的是，题⽬中要求找到所有「不重复」的三元组。那我们可以利⽤在两数之和那⾥⽤的双指针思想，来对我们的暴⼒枚举做优化：
i. 先排序；
ii. 然后固定⼀个数 a ；
iii. 在这个数后⾯的区间内，使⽤「双指针算法」快速找到两个数之和等于 -a 即可。
但是要注意的是，这道题⾥⾯需要有「去重」操作：
i. 找到⼀个结果之后， left 和 right 指针要「跳过重复」的元素；
ii. 当使⽤完⼀次双指针算法之后，固定的 a 也要「跳过重复」的元素。
图解
代码
public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> ret = new ArrayList<>();//用来存放满足条件的所有数组[[nums[i],nums[left],nums[right]],[nums[i],nums[left],nums[right]],[nums[i],nums[left],nums[right]],....]//1.先排序（升序）Arrays.sort(nums);//2.先固定一个数i，再利用“双指针算法”去寻找i后面的区间中的能够相加等于-i的两个数int n = nums.length;//因为i在去重这一步会进行i++，来判断nums[i]是否等于nums[i-1],所以for循环的条件表达式中省略了i++for(int i = 0;i < n;){//判断nums[i]此时的值是否大于零，因为整个数组是事先进行顺序排序的，当nums[i]后面包括nums[i]本身大于零，那么后面进行双指针时，是找不到两数和为负数的情况的，也就没有必要继续找了，这是一个小优化！if(nums[i] > 0){break;}//在nums[i]后⾯的区间内，使⽤「双指针算法」快速找到两个数之和等于 -nums[i] 即可。跟两数之和一样，可以利用单调性来优化算法int left = i + 1;//left必须在固定的值i的左区间中int right = n - 1;int target = -nums[i];while(left < right){int sum = nums[left] + nums[right];//sum小于target，此时的left是最小值，right是最大值，两者和sum都小于target了，那么left和right左边的数相加的和，必定是小于target的，所以让left向右移动一位即可，没必要继续枚举//sum大于target，此时的right是最大值，而left是最小值，所以是因为right太大了，就要将right向左移动一位if(sum < target){left++;}else if(sum > target){right--;}else{ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[left],nums[right])));left++;right--;//缩小区间继续查找//找到⼀个结果之后， left 和 right 指针要「跳过重复」的元素,也就是去重，可以优化算法时间复杂度while(left < right && nums[left] == nums[left - 1]){left++;}while(left < right && nums[right] == nums[right + 1]){right--;}}}//去重：i，i++后也有可能会等于前一个i所指向的下标的值，所以，当nums[i]==nums[i-1]时，可以让i直接向后移动直到nums[i]！=nums[i-1]为止i++;//此处直接让i++,判断nums[i]是否等于nums[i-1]//i也需要确保不能越界while(i < n && nums[i] == nums[i - 1] ){i++;}}return ret;
}