vvrf / DSA.log

问题拆解

在数组里找出所有和为 0 的三元组，要求结果不含重复的三元组。

三重循环枚举是 O(n³)，且去重要么排序每个三元组塞进集合，要么逐个比对，都很笨重。突破口是先把数组排序：固定第一个数 nums[i] 后，问题退化成“在 i 右侧的有序区间里找两数之和等于 -nums[i]”——有序数组上的两数之和用左右双指针 O(n) 就能解决：和太小左指针右移，和太大右指针左移。

排序换来两件事：双指针能按大小关系单向移动，重复元素相邻排列——去重只需比较邻居。

去重恰恰是这道题的主要难点，它分散在三个位置：固定的 i、左指针 left、右指针 right，漏掉任何一处都会产出重复三元组。

排序 + 固定一数 + 双指针

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    int n = nums.length;
    for (int i = 0; i < n - 2; i++) {
        if (nums[i] > 0) break; // 最小的数已大于 0，后面不可能凑出 0
        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) {
                left++;
            } else if (sum > 0) {
                right--;
            } else {
                res.add(List.of(nums[i], nums[left], nums[right]));
                left++;
                right--;
                // 去重二、三：命中后跳过两侧的重复值
                while (left < right && nums[left] == nums[left - 1]) left++;
                while (left < right && nums[right] == nums[right + 1]) right--;
            }
        }
    }
    return res;
}

def threeSum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    res = []
    n = len(nums)
    for i in range(n - 2):
        if nums[i] > 0:
            break  # 最小的数已大于 0，后面不可能凑出 0
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # 去重一：跳过重复的固定数
        left, right = i + 1, n - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if s < 0:
                left += 1
            elif s > 0:
                right -= 1
            else:
                res.append([nums[i], 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
    return res

func threeSum(nums []int) [][]int {
    slices.Sort(nums)
    res := [][]int{}
    n := len(nums)
    for i := 0; i < n-2; i++ {
        if nums[i] > 0 {
            break // 最小的数已大于 0，后面不可能凑出 0
        }
        if i > 0 && nums[i] == nums[i-1] {
            continue // 去重一：跳过重复的固定数
        }
        left, right := i+1, n-1
        for left < right {
            sum := nums[i] + nums[left] + nums[right]
            switch {
            case sum < 0:
                left++
            case sum > 0:
                right--
            default:
                res = append(res, []int{nums[i], nums[left], nums[right]})
                left++
                right--
                // 去重二、三：命中后跳过两侧的重复值
                for left < right && nums[left] == nums[left-1] {
                    left++
                }
                for left < right && nums[right] == nums[right+1] {
                    right--
                }
            }
        }
    }
    return res
}

pub fn three_sum(nums: Vec<i32>) -> Vec<Vec<i32>> {
    let mut nums = nums;
    nums.sort_unstable();
    let mut res = Vec::new();
    let n = nums.len();
    if n < 3 {
        return res;
    }
    for i in 0..n - 2 {
        if nums[i] > 0 {
            break; // 最小的数已大于 0，后面不可能凑出 0
        }
        if i > 0 && nums[i] == nums[i - 1] {
            continue; // 去重一：跳过重复的固定数
        }
        let (mut left, mut right) = (i + 1, n - 1);
        while left < right {
            let sum = nums[i] + nums[left] + nums[right];
            if sum < 0 {
                left += 1;
            } else if sum > 0 {
                right -= 1;
            } else {
                res.push(vec![nums[i], nums[left], nums[right]]);
                left += 1;
                right -= 1;
                // 去重二、三：命中后跳过两侧的重复值
                while left < right && nums[left] == nums[left - 1] {
                    left += 1;
                }
                while left < right && nums[right] == nums[right + 1] {
                    right -= 1;
                }
            }
        }
    }
    res
}

三处去重各有讲究。去重一比较的是 nums[i] 和 nums[i-1]（前一个位置），而不是 nums[i+1]——写成后者会把 [-1, -1, 2] 这类“固定数自身重复但三元组合法”的答案错杀。去重二、三放在命中之后执行：先把这组答案收下、指针各走一步，再跳过与刚才相同的值；若把跳过逻辑放在移动之前，left 与 left - 1 比较的还是同一组答案里的数，边界很容易乱。另外 nums[i] > 0 的剪枝依赖排序后固定数是三者最小：连最小的都是正数，三数之和必大于 0，可以直接收工。

复杂度

指标	复杂度	原因
时间	`O(n²)`	排序 O(n log n)，外层固定一数 O(n)，内层双指针合计 O(n)
空间	`O(log n)`	排序的栈开销，结果数组不计

可以迁移的模式

k 数之和的通用降维法：排序后固定前 k-2 个数，最内层交给双指针，四数之和（18）同款；
有序数组上的去重不需要哈希集合，跳过相邻重复值就够，还是 O(1) 空间；
“固定一端 + 双指针夹逼”要求单调性支撑指针的单向移动，这正是排序买来的性质。

把“去重”从事后过滤变成枚举过程中的跳过，是这道题从会做到写对的分水岭。