本文详解 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>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<list>> result = new ArrayList();
    int n = nums.length;

    for (int i = 0; i  0 && nums[i] == nums[i - 1]) continue;

        int left = i + 1, right = n - 1;
        while (left <p>? <strong>核心优化点解析</strong>：</p>
<ul>
<li>
<strong>O(1) 去重替代 O(k) 查找</strong>：通过 nums[i] == nums[i-1]、nums[left] == nums[left+1] 等条件，在遍历中直接跳过重复数字，完全避免 contains() 调用；</li>
<li>
<strong>边界剪枝</strong>：外层循环只需到 n-2，内层 left </li>
<li>
<strong>空间友好</strong>：不额外使用 Set 或临时数组，仅用 List<list>> 存储结果，符合题目返回格式。</list>
</li>
</ul>
<p>⚠️ 注意事项：</p>
<ul>
<li>切勿在循环内创建 ArrayList 后调用 contains() —— 这是 TLE 主因（测试用例 311 包含上万元素，重复三元组极多）；</li>
<li>Arrays.asList() 返回不可变列表，但本题中用于构造结果无副作用，安全；</li>
<li>若需极致性能（如海量重复数据），可考虑用 Set<list>> 收集再转 List，但实际中双指针跳过法更优且简洁。</list>
</li>
</ul>
<p>? 进阶思考：部分解法尝试用二分搜索替代右指针移动（如 Arrays.binarySearch(nums, mid+1, n, target)），虽理论单次查找为 O(log n)，但双重循环下仍为 O(n² log n)，且常数因子更大，实践中双指针的 O(n²) 更稳定高效。</p>
<p>总结：ThreeSum 的最优解 = <strong>排序预处理 + 外层定基 + 内层双指针收缩 + 重复值前向跳过</strong>。掌握这一范式，不仅能通过 LeetCode，更是理解“利用有序性消除暴力枚举”的经典算法思维。</p></list></list>