题目

截图来自官方

 

这道题对于重复数据的消除的思想需要掌握

代码

class Solution { // 本题很经典，需要牢牢掌握。 // 注意理解官方思路 // 本质上大框架是先将给的数组从小到大排序，然后使用三重for循环遍历，遍历过程中跨过重复的数据来去除重复的结果。 // 最终版本的代码可以对第二三层循环做优化，用双指针的思想让他们两个从左右逼近（因为first不变且second增加时，还想满足sum=0，则third必须减小）将第三层改为while循环来减小third，时间复杂度由O(n^3)降为O(n^2)。 // 但是记着第一层for循环时要将third重新置为最右端。 public List<List<Integer>> threeSum(int[] nums) { int n=nums.length; // third不能定义到这里，定义到这里会使最终结果少很多值。应该定义到第一个for中。例子：给定[-4,-3,-2,-1,-1,0,0,1,2,3,4] // int third=n-1; List<List<Integer>> res=new ArrayList(); // 直接修改了nums,从小到大 Arrays.sort(nums); for(int first=0;first<n;first++){ // 下面的if逻辑错了，很细节。按下面来说，first为0时直接不进入了都。 // if(first!=0&&nums[first]!=nums[first-1]){ // 修改1 if(first!=0&&nums[first]==nums[first-1]){ continue; } // 修改2 int third=n-1; for(int second=first+1;second<n;second++){ // 同理，这里也错了 // if(second!=first+1&&nums[second]!=nums[second-1]){ // 是允许second==first+1的；比如【0，0，0】就是一组结果 if(second!=first+1&&nums[second]==nums[second-1]){ continue; } while(second<third&&nums[first]+nums[second]+nums[third]>0){ third--; } // 元素不可以重合 if(third==second){ break; } // 必须有这个if，因为有可能上一个while后三个加起来直接小于0了（没有等于0的值） if(nums[first]+nums[second]+nums[third]==0){ List<Integer> temp=new ArrayList(); temp.add(nums[first]); temp.add(nums[second]); temp.add(nums[third]); res.add(temp); } // } } // } } return res; } }