1. 三数之和（15）如何排序+双指针+去重避免超时
问题
三数之和（LeetCode 15）如何用排序 + 双指针 + 去重来避免超时？
考察点
- 排序 + 双指针
- 去重策略
- 去重策略：固定一个数后，对左右指针值去重，避免重复三元组
答案
先对数组排序，然后固定第一个数 nums[i]，用左右双指针在 i 右侧找两个数使其和为 -nums[i]。因为排序后双指针可单调收缩：和小于目标则左指针右移，大于则右指针左移。同时用"跳过重复值"去重：固定 i 时若 nums[i]==nums[i-1] 跳过；找到一组解后，左右指针跳过重复值再继续。这样复杂度 O(n²)（排序 O(n log n) + 双指针 O(n²)），比暴力三重循环 O(n³) 快得多，是标准解法。
解析
排序使双指针可行（单调性依据），也便于去重。双指针在有序数组上找两数和可用 O(n)，固定 i 后对每个 i 做一次 O(n) 双指针，总 O(n²)。去重通过"跳过与上一个相同的元素"避免重复三元组，避免输出重复结果。
示例代码
List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重
int l = i + 1, r = nums.length - 1, target = -nums[i];
while (l < r) {
int s = nums[l] + nums[r];
if (s == target) {
res.add(Arrays.asList(nums[i], nums[l], nums[r]));
while (l < r && nums[l] == nums[l + 1]) l++; // 去重
while (l < r && nums[r] == nums[r - 1]) r--;
l++; r--;
} else if (s < target) l++;
else r--;
}
}
return res;
}