解法：双指针优化
解题思路
暴力法搜索为O(N^3)时间复杂度，可通过双指针动态消去无效解来优化效率。
算法流程
- 先将
nums排序，时间复杂度为 O(NlogN)
- 固定 3 个指针中最左（最小）元素的指针 k，双指针 i,j 分设在数组索引 (k, len(nums))两端。
- 双指针 i,j 交替向中间移动，记录每个固定指针 k 的所有满足
nums[k] + nums[i] + nums[j] == 0的 i,j 组合： - 当
nums[k] > 0时直接 break 跳出：因为排序后nums[j] >= nums[i] >= nums[k] > 0，即 3个元素都大于0 ，在此固定指针 k 之后不可能再找到结果了。 - 当
k > 0且nums[k] == nums[k - 1]时即跳过此元素nums[k]：因为已经将nums[k - 1]的所有组合加入到结果中，本次双指针搜索只会得到重复组合。 - i,j 分设在数组索引 (k,len(nums)) 两端，当 i<j 时循环计算
s = nums[k] + nums[i] + nums[j]，并按照以下规则执行双指针移动： - 当 s < 0 时，i ++ 并跳过所有重复的 nums[i]；
- 当 s > 0 时，j — 并跳过所有重复的 nums[j]；
- 当 s == 0 时，记录组合 [k, i, j] 至 res，执行 i ++ 和 j — 并跳过所有重复的 nums[i] 和 nums[j]，防止记录到重复组合。
代码
class Solution { public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); List<List<Integer>> res = new ArrayList<>(); for(int k = 0; k < nums.length - 2; k++){ if(nums[k] > 0) break; if(k > 0 && nums[k] == nums[k - 1]) continue; int i = k + 1, j = nums.length - 1; while(i < j){ int sum = nums[k] + nums[i] + nums[j]; if(sum < 0){ while(i < j && nums[i] == nums[++i]); } else if (sum > 0) { while(i < j && nums[j] == nums[--j]); } else { res.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[i], nums[j]))); while(i < j && nums[i] == nums[++i]); while(i < j && nums[j] == nums[--j]); } } } return res; } }
细节
在移动 i,j 的时候要注意再次判断是否交错，否则可能出现越界的问题
while(i < j && nums[i] == nums[++i]); while(i < j && nums[j] == nums[--j]);
这种判重剪枝同时移动下标的写法值得学习
另外，注意在确定k时的剪枝优化：如果k>0直接跳出，如果下一个重复进入下一次循环
