3Sum

返回所有和为 0 的不重复三元组。

返回所有和为 0 的不重复三元组。真正的模式是先排序，再把内层搜索变成双指针扫描。

ArrayTwo Pointers

题目定位

排序之后，内层 pair 搜索就能变成可控的双指针扫描，而外层循环只负责固定一个数。

关键观察

数组有序后，剩余两个数的移动方向完全由当前和偏小还是偏大决定。

目标复杂度

O(n^2) / O(1)

这题的解法思路怎么拆

先排序，这样去重和指针移动都会变得可控。

固定下标 i 处的数字，把问题转成后缀区间上的 two-sum。

用左右指针搜索剩下两个数。

外层循环和内层指针都要跳过重复值。

拿一个例子顺一遍

例如 [-1, 0, 1, 2, -1, -4] 排序后变成 [-4, -1, -1, 0, 1, 2]。

固定 index 1 的 -1，再在后缀里用 left = 2、right = 5 做双指针搜索。

可以找到 [-1, -1, 2] 和 [-1, 0, 1]，并在移动时顺手跳过重复值。

后面的 anchor 不会再产生新的不重复三元组。

参考实现

Python

def threeSum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    answer: list[list[int]] = []

    for index in range(len(nums) - 2):
        if index > 0 and nums[index] == nums[index - 1]:
            continue

        left, right = index + 1, len(nums) - 1
        while left < right:
            total = nums[index] + nums[left] + nums[right]
            if total == 0:
                answer.append([nums[index], nums[left], nums[right]])
                left += 1
                right -= 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1

    return answer