双指针-三数之和

三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。 注意：答案中不可以包含重复的三元组。

输入：整型数组 输出：二元列表 思路：先对数组进行排序，然后循环排序后的数组，再定义双指针，进行移动，关键是对于去重的操作，

class Solution { public List<List<Integer>> threeSum(int[] nums) { //定义返回值的二元列表 List<List<Integer>> result = new ArrayList<>(); //先对数组nums进行排序 Arrays.sort(nums); //当第一个数值大于0，则直接返回 if(nums[0] > 0){ return result; } //然后进行for循环遍历每一个数组元素 for(int i = 0;i < nums.length;i++){ //定义双指针 int l = i + 1; int r = nums.length - 1; if (i > 0 && nums[i] == nums[i - 1]) { // 去重a continue; } //应该在循环中不断变换双指针 while(l < r){ //判断值与零的大小关系 if(nums[i] + nums[l] + nums[r] > 0){ //说明右边大了 r--; }else if(nums[i] + nums[l] + nums[r] < 0){ //说明左边小了 l++; }else{ //说明等于0 result.add(new ArrayList<>(Arrays.asList(nums[i],nums[l],nums[r]))); while (r > l && nums[r] == nums[r - 1]) r--; while (r > l && nums[l] == nums[l + 1]) l++; r--; l++; } } } return result; } }

去重逻辑的思考 其实就是左中右三个数的去重，i，l，r索引所对应的值

对于i的去重应该使用nums[i] == nums[i-1]判断，如果写成 if (nums[i] == nums[i + 1]) { // 去重操作 continue; }

那我们就把 三元组中出现重复元素的情况直接pass掉了。 例如{-1, -1 ,2} 这组数据，当遍历到第一个-1 的时候，判断 下一个也是-1，那这组数据就pass了。 那么应该这么写：

if (i > 0 && nums[i] == nums[i - 1]) { continue; }

这么写就是当前使用 nums[i]，我们判断前一位是不是一样的元素，在看 {-1, -1 ,2} 这组数据，当遍历到 第一个 -1 的时候，只要前一位没有-1，那么 {-1, -1 ,2} 这组数据一样可以收录到 结果集里。

只有在三数之和等于零是才有可能出现重复的情况，所以以下逻辑不合理，并无卵用 while (right > left) { if (nums[i] + nums[left] + nums[right] > 0) { right--; // 去重 right while (left < right && nums[right] == nums[right + 1]) right--; } else if (nums[i] + nums[left] + nums[right] < 0) { left++; // 去重 left while (left < right && nums[left] == nums[left - 1]) left++; } else { } }