前置知识点：排序 + 双指针

数组排序

将无序数组变为有序，是使用对向双指针的前提。排序后可以利用有序性，通过指针移动快速缩小查找范围，避免暴力枚举的 O(n³) 复杂度。Python 实现：nums.sort() 原地排序，时间复杂度 O(n log n)。

对向双指针（左右指针）

固定一个基准元素，在其右侧子数组中用 left 和 right 指针向中间逼近。根据三数之和与目标值的大小关系，移动指针：

• 和 > 目标值 → right 左移（减小和）
• 和 < 目标值 → left 右移（增大和）
• 和 = 目标值 → 记录结果，并跳过重复值

时间复杂度：O(n²)（排序 O(n log n) + 双指针遍历 O(n²)）。空间复杂度：O(1)（原地排序，仅用常数额外空间）。

去重技巧

• 基准元素去重：若当前元素与前一个相同，直接跳过，避免生成重复三元组。
• 结果元素去重：找到符合条件的三元组后，继续移动 left 和 right 指针，跳过所有与当前结果相同的元素。

经典算法题：三数之和（LeetCode 15）

题目描述

给定一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k，同时满足 nums[i] + nums[j] + nums[k] = 0。返回所有和为 0 且不重复的三元组。

示例：
输入：nums = [-1, 0, 1, 2, -1, -4]
输出：[[-1, -1, 2], [-1, 0, 1]]

最优解法：排序 + 双指针

from typing import List

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()  # 先排序，方便双指针查找
        n = len(nums)
        for i in range(n - 2):
            if i > 0 and nums[i] == nums[i - 1]:  # 跳过基准元素的重复值
                continue
            if nums[i] > 0:  # 第一个数 >0，后面不可能和为0
                break
            left = i + 1
            right = n - 1
            while left < right:
                total = nums[i] + nums[left] + nums[right]
                if total < 0:
                    left += 1  # 和太小，左指针右移
                elif total > 0:
                    right -= 1  # 和太大，右指针左移
                else:
                    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
        return res

代码执行示例

以 nums = [-1, 0, 1, 2, -1, -4] 为例：

1. 排序后：[-4, -1, -1, 0, 1, 2]
2. i=0（nums[i]=-4）：
   • left=1, right=5 → 和为 -4 + (-1) + 2 = -3 < 0 → left++
   • 最终无法找到和为 4 的组合，无结果
3. i=1（nums[i]=-1）：
   • left=2, right=5 → 和为 -1 + (-1) + 2 = 0 → 记录 [-1, -1, 2]
   • 跳过重复后 left=3, right=4 → 和为 -1 + 0 + 1 = 0 → 记录 [-1, 0, 1]
4. i=2：与 i=1 重复，直接跳过
5. i=3（nums[i]=0）：0 > 0 不成立，但后续元素均 >0，无法和为 0，循环结束
6. 最终结果：[[-1, -1, 2], [-1, 0, 1]]

关键知识点总结

时间复杂度分析

• 排序：O(n log n)
• 双指针遍历：外层循环 O(n)，内层双指针遍历 O(n)，总计 O(n²)
• 整体：O(n log n) + O(n²) = O(n²)，远优于暴力法 O(n³)

去重逻辑详解

• 基准去重：if i > 0 and nums[i] == nums[i-1] → 避免以相同数字作为第一个数，生成重复三元组。
• 结果去重：找到和为 0 的三元组后，继续移动 left 和 right 指针，跳过所有与当前 left/right 相同的元素，避免同一组数字生成多次结果。

剪枝优化

当 nums[i] > 0 时，由于数组已排序，后续元素均 ≥ nums[i]，三数之和必然 > 0，直接 break 终止循环。

双指针法在 n 数之和中的通用思路