本文详解 ThreeSum 问题的最优解法：通过排序 + 双指针消除重复、避免低效的 contains() 检查，并分析二分搜索等进阶优化思路，将时间复杂度从 O(n³) 降至 O(n²)，彻底规避超时（TLE）。
本文详解 threesum 问题的最优解法：通过排序 + 双指针消除重复、避免低效的 `contains()` 检查，并分析二分搜索等进阶优化思路，将时间复杂度从 o(n³) 降至 o(n²)，彻底规避超时（tle）。
ThreeSum 是 LeetCode 经典难题（#15），核心挑战在于去重与效率。原始代码虽采用排序 + 双指针框架，但存在两个致命性能缺陷：一是使用 ans.contains(temp) 进行线性查找——每次调用耗时 O(k)，其中 k 为已存三元组数量，整体退化为 O(n³)；二是未跳过重复元素，导致大量无效计算和冗余判断。
✅ 正确解法的关键在于：利用排序特性，在指针移动时主动跳过重复值，而非事后去重。以下是标准双指针优化实现：
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
int n = nums.length;
for (int i = 0; i < n - 2; i++) {
// 跳过重复的 nums[i]，避免重复三元组
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1, right = n - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
// 关键：左右指针同时跳过重复值
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}? 核心优化点解析：
- O(1) 去重替代 O(k) 查找：通过 nums[i] == nums[i-1]、nums[left] == nums[left+1] 等条件，在遍历中直接跳过重复数字，完全避免 contains() 调用；
- 边界剪枝：外层循环只需到 n-2，内层 left
-
空间友好：不额外使用 Set 或临时数组，仅用 List
- > 存储结果，符合题目返回格式。
⚠️ 注意事项：
- 切勿在循环内创建 ArrayList 后调用 contains() —— 这是 TLE 主因（测试用例 311 包含上万元素，重复三元组极多）；
- Arrays.asList() 返回不可变列表，但本题中用于构造结果无副作用，安全；
- 若需极致性能（如海量重复数据），可考虑用 Set
- > 收集再转 List，但实际中双指针跳过法更优且简洁。
? 进阶思考：部分解法尝试用二分搜索替代右指针移动（如 Arrays.binarySearch(nums, mid+1, n, target)），虽理论单次查找为 O(log n)，但双重循环下仍为 O(n² log n)，且常数因子更大，实践中双指针的 O(n²) 更稳定高效。
总结：ThreeSum 的最优解 = 排序预处理 + 外层定基 + 内层双指针收缩 + 重复值前向跳过。掌握这一范式，不仅能通过 LeetCode，更是理解“利用有序性消除暴力枚举”的经典算法思维。
