这本来是做双指针的16题 最近三数之和，发现这个题目和著名的三数之和很像，所以就返回来先做这个了。
其实思路讲出来还蛮简单的。原本需要3轮for循环，但我们可以在第一轮for循环后，剩下的两重for循环采用排序+双指针的方式做，这样的话，时间复杂度由On3变为On2。
这里需要注意的是：
去重需要从好几个地方考虑，如果i，j，k在移动时出现相等的值时都需要去重（不添加）
先看下我写的极其麻烦的代码：
import java.util.Arrays; class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> result=new ArrayList<List<Integer>>(); Arrays.sort(nums); for(int i=0;i<nums.length;i++)//看这里具体是小于多少 { if (i > 0 && nums[i] == nums[i - 1]) { continue; }//避免重复 int targetNew=-nums[i]; int j=i+1,k=nums.length-1; while(k>j) { if(nums[j]+nums[k]>targetNew) { k--;} else if(nums[j]+nums[k]<targetNew) {j++;} else if(nums[j]+nums[k]==targetNew) { //避免重复 if(j==i+1) { if(k==nums.length-1) {result.add(Arrays.asList(nums[i],nums[j],nums[k]));} else { if(nums[k]!=nums[k+1]) { result.add(Arrays.asList(nums[i],nums[j],nums[k])); } } } else { if(k==nums.length-1) { if(nums[j]!=nums[j-1]) { result.add(Arrays.asList(nums[i],nums[j],nums[k])); } } else { if(nums[k]!=nums[k+1]||nums[j]!=nums[j-1]) { result.add(Arrays.asList(nums[i],nums[j],nums[k]));} } } k--; j++; //添加i,j,k这组到结果中 } } } return result; } }
主要是在双指针阶段，由于要判断 j和j-1是否相等，k和k+1是否相等，以及j-1是否越界，k+1是否越界，所以搞出来这个判断。
但实际上可以在出现一次正确结果时先尝试着移动指针，跳过那些可能的重复
import java.util.Arrays; class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> result=new ArrayList<List<Integer>>(); Arrays.sort(nums); for(int i=0;i<nums.length;i++)//看这里具体是小于多少 { if (i > 0 && nums[i] == nums[i - 1]) { continue; }//避免重复 int targetNew=-nums[i]; int j=i+1,k=nums.length-1; while(k>j) { if(nums[j]+nums[k]>targetNew) { k--;} else if(nums[j]+nums[k]<targetNew) {j++;} else if(nums[j]+nums[k]==targetNew) { result.add(Arrays.asList(nums[i],nums[j],nums[k])); j++;//注意要移动指针啊 k--; while(j<k&&nums[j]==nums[j-1])//这里是去重的关键 {j++;} while(k>j&&nums[k]==nums[k+1]) {k--;} } } } return result; } }
原文：https://www.cnblogs.com/take-it-easy/p/13821056.html