LeetCode三数之和问题更优解法咨询及二分实现代码评审

复杂度标注问题 #

你标注的O(nlogn)时间复杂度、O(1)额外空间复杂度都是不准确的：

• 时间复杂度层面：前置排序的开销确实是O(nlogn)，但外层固定第一个数的循环是O(n)量级，内层循环哪怕加入了mid做二分跳步，最坏场景下（比如连续整数序列、全0数组这类测试用例）指针仍然需要逐次移动，内层遍历开销是O(n)量级，整体最坏时间复杂度是O(n²)。目前基于比较的通用3Sum解法理论下界就是O(n²)，不存在O(nlogn)的通用实现，你加的二分跳步属于常数级优化，没有改变时间复杂度的量级。
• 空间复杂度层面：如果不算返回的结果集，Java中Arrays.sort对int数组使用的双轴快排递归栈需要O(logn)的额外空间，达不到O(1)；如果把结果集算入空间占用，最坏情况下合法三元组数量是O(n²)量级，空间开销会更高。只有采用非递归原地排序、且不计算结果集空间时，才能做到O(1)额外空间。

现有代码的具体问题 #

• 去重逻辑存在漏解和冗余判断：找到合法三元组后，你只做了left++操作，没有同步移动right指针，随后直接对right做向前去重判断，相当于把当前匹配到的right值直接跳过了，在存在多组不同left对应同一个right值的场景下会漏解；同时right的去重判断没有先移动指针，在连续重复值较长时会出现大量无用判断。
• 二分跳步的边界判断不严谨：当三数和小于0时，你判断mid位置值和right、firstValue的和小于0就直接把left跳到mid+1，在数组存在大量连续重复值时，可能直接跳过刚好能凑成0的left位置，导致漏解；三数和大于0时的右指针跳步也存在同类问题。
• 兼容性问题：代码中使用的List.of()是Java 9及以上版本才支持的API，在LeetCode默认的Java 8环境下会直接编译报错，需要替换为Arrays.asList()。

优化方向 #

目前通用场景下排序+双指针的思路已经是3Sum的最优比较类解法，可以通过几个细节优化提升实际运行效率：

• 增加提前剪枝逻辑：外层循环遍历第一个数时，如果当前第一个数已经大于0，后面所有数都大于等于它，三数和必然大于0，可以直接break外层循环；如果当前第一个数加上数组末尾两个最大数的和仍然小于0，说明这个数太小，不可能凑出0，直接continue跳过当前轮次即可。
• 修正去重逻辑：找到合法三元组后，先同时移动left和right指针，再跳过重复值，避免越界和漏解。
• 二分跳步逻辑可以保留，但要增加边界校验，跳步后不要直接跨过可能匹配的区间，修正后在重复值较多的测试用例下，运行效率会比普通双指针实现快10%~20%左右，但本质还是O(n²)时间复杂度的解法。

内容的提问来源于stack exchange，提问作者IkhideIfidon