如何优化LeetCode 3Sum问题？从暴力超时到双指针高效解法的完整思路

LeetCode上的3Sum问题要求从整数数组中找出所有不重复的三元组，使得三者之和为0。最直接的想法是三层循环枚举所有组合，但这种方法在数组规模稍大时就会超时。真正合理的做法是借助排序和双指针，将时间复杂度从立方级降到平方级，同时利用有序性完成去重。

为什么暴力解法会超时

如果我们不对数组做任何预处理，使用三重循环依次固定第一个数、第二个数和第三个数，那么对于任意长度为n的数组，需要检查的组合数量为C(n,3)，近似于n³/6。当n达到3000时，循环次数接近45亿次，远超多数在线评测系统的时间限制。而且暴力法在找到和为0的组合后，还需要额外用哈希集合判断是否重复，进一步拖慢运行速度。

另一个容易被忽略的问题是，暴力法每次都要重新扫描剩余元素，无法利用任何已知的大小关系。比如当数组已经有序时，若前两个数之和已经大于0，那么第三个数无论取什么正值都不可能让总和为0，但三层循环仍然会机械地往后走。这种大量无效搜索正是超时的根源。

排序加双指针的核心原理

双指针解法的第一步是对原数组进行升序排序，时间复杂度为O(n log n)。排序后，我们可以固定第一个数nums[i]，然后在i+1到n-1的区间上使用左指针left和右指针right。由于数组有序，当nums[i]+nums[left]+nums[right]小于0时，说明整体和偏小，只能将left右移增大数值；当和大于0时，将right左移减小数值。这样内层只需要线性扫描，外层遍历n次，总复杂度为O(n²)。

去重也是双指针法的天然优势。固定数nums[i]时，如果它和前一个数相等，可以直接跳过，因为以它为起点的所有合法组合已经被上一轮找过。左右指针在找到一组解后，也要分别跳过相邻的相同值，避免把同一组数字重复加入结果。下面给出Python实现：

def threeSum(nums):
    nums.sort()  # 先排序，时间复杂度O(nlogn)
    res = []
    n = len(nums)
    for i in range(n):
        # 跳过重复的固定值
        if i > 0 and nums[i] == nums[i-1]:
            continue
        left = i + 1
        right = n - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if s == 0:
                res.append([nums[i], nums[left], nums[right]])
                # 左右指针跳过重复值
                while left < right and nums[left] == nums[left+1]:
                    left += 1
                while left < right and nums[right] == nums[right-1]:
                    right -= 1
                left += 1
                right -= 1
            elif s < 0:
                left += 1
            else:
                right -= 1
    return res

Java版本与边界细节

在Java中实现时，同样要先排序，然后使用Arrays.sort方法。需要注意的是，当数组长度小于3时应直接返回空列表，而对指针的移动必须严格保证left小于right，否则会出现越界。下面的代码展示了完整的处理逻辑：

import java.util.*;

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length < 3) return ans;
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) {
            if (i > 0 && nums[i] == nums[i-1]) continue;
            // 最小三数之和已大于0，后面无需再试
            if (nums[i] + nums[i+1] + nums[i+2] > 0) break;
            // 最大三数之和仍小于0，当前i太小
            if (nums[i] + nums[n-1] + nums[n-2] < 0) continue;
            int left = i + 1, right = n - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    ans.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 ans;
    }
}

上面的Java代码还增加了两个剪枝判断：如果当前数与后面两个最小数之和已经大于0，由于数组有序，后面不可能再有合法组合，直接结束循环；如果当前数与两个最大数之和仍小于0，说明当前数太小，直接进入下一次外层循环。这种提前退出能进一步减少不必要的指针移动。

复杂度与常见误区

经过排序和双指针优化后，时间复杂度由O(n³)降为O(n²)，空间复杂度主要来自排序的栈空间O(log n)以及结果存储。很多初学者误以为双指针只能用于有序数组的求和，其实只要问题具备单调性，比如一端增大另一端就必须减小，就可以考虑这种思路。另外，有人喜欢用哈希表代替双指针，但在需要处理大量去重场景时，哈希表不仅占用更多内存，代码也更容易写出重复逻辑的漏洞。

还有一个常见错误是在去重时只跳过右指针或只跳过左指针，导致结果中仍然出现重复三元组。正确做法是在找到一组解后，左右指针都要向中间收缩并跨过所有相等元素。只要把握住排序、固定、双指针对撞、双向去重这四个环节，3Sum就能从超时变为稳定通过的题目。

3Sum双指针LeetCode优化修改时间：2026-08-05 18:33:29