文章目录
- 题目
- 我的代码(超时)
- 官方题解
- 问题
- 深入理解
- 总结
题目
三数之和
我的代码(超时)
classSolution{publicList<List<Integer>>threeSum(int[]nums){List<List<Integer>>list=newArrayList<>();intn=nums.length;Arrays.sort(nums);for(inti=0;i<n;i++){if(i>0&&nums[i]==nums[i-1]){continue;}for(intj=i+1;j<n;j++){if(j>i+1&&nums[j]==nums[j-1]){continue;}for(intk=n-1;k>=j+1;k--){if(k<n-1&&nums[k]==nums[k+1]){continue;}if(nums[k]>-nums[i]-nums[j]){continue;}if(nums[k]<-nums[i]-nums[j]){break;}list.add(Arrays.asList(nums[i],nums[j],nums[k]));}}}returnlist;}}官方题解
classSolution{publicList<List<Integer>>threeSum(int[]nums){intn=nums.length;Arrays.sort(nums);List<List<Integer>>ans=newArrayList<List<Integer>>();// 枚举 afor(intfirst=0;first<n;++first){// 需要和上一次枚举的数不相同if(first>0&&nums[first]==nums[first-1]){continue;}// c 对应的指针初始指向数组的最右端intthird=n-1;inttarget=-nums[first];// 枚举 bfor(intsecond=first+1;second<n;++second){// 需要和上一次枚举的数不相同if(second>first+1&&nums[second]==nums[second-1]){continue;}// 需要保证 b 的指针在 c 的指针的左侧while(second<third&&nums[second]+nums[third]>target){--third;}// 如果指针重合，随着 b 后续的增加// 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环if(second==third){break;}if(nums[second]+nums[third]==target){List<Integer>list=newArrayList<Integer>();list.add(nums[first]);list.add(nums[second]);list.add(nums[third]);ans.add(list);}}}returnans;}}问题
这个官方答案似乎没有限制最后一层循环的指针不能和上一次元素一样吧？
深入理解
噢，因为我写的是三重循环，所以如果满足答案了，会移动右边的指针往左，但是必须判断重复因为有可能会重复，而官方用了双指针，如果满足答案会移动左指针，而左指针本来就已经判断重复了，所以肯定会是新的答案？其实应该说如果满足答案，既移动左指针也移动右指针？因为左指针移动到一个新的数，想要再满足答案，右指针也必须移动
你的理解 完全正确！
我给你总结成 3 句终极真理：
- 为什么 官方双指针不需要给 third（右指针）去重？
因为：找到答案后，程序会自动让 second（左指针）往前走而 second 已经做过去重了→ 下一个 second 一定是新数字→ 就算 third 不动，组合也一定是新答案→ 不可能重复！
所以官方根本不需要给 third 去重。 - 为什么 你的三重循环必须给 third 去重？
因为：你是 暴力枚举所有 j 和 k即使找到一组答案k 还会继续往左走可能走到相同数字例如：
[-1, -1,2,2]你会找到：
[-1,-1,2]（k=3）[-1,-1,2]（k=2）重复了！
所以 你必须给 k 去重，你写的是对的！
3. 你最后这句是 满分理解！
你说：
其实应该说如果满足答案，既移动左指针也移动右指针？因为左指针移动到一个新的数，想要再满足答案，右指针也必须移动
完全正确！标准双指针找到答案后应该：
second++ third--因为：
左指针右移 → 数字变大
右指针左移 → 数字变小
才能继续寻找下一组不重复的解
这就是双指针能去重的根本原因！
最终终极结论（你可以牢牢记住）
✔ 你是对的！
✔ 三重循环必须给 third 去重
✔ 双指针不需要给 third 去重（因为 second 已经去重）
✔ 找到解后，双指针应该两边一起移动 才能继续找下一组不重复解
总结
这个方法就是我们常说的「双指针」，当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法，将枚举的时间复杂度从 O(N
2
) 减少至 O(N)。为什么是 O(N) 呢？这是因为在枚举的过程每一步中，「左指针」会向右移动一个位置（也就是题目中的 b），而「右指针」会向左移动若干个位置，这个与数组的元素有关，但我们知道它一共会移动的位置数为 O(N)，均摊下来，每次也向左移动一个位置，因此时间复杂度为 O(N)。
