leetcode-go/双指针/06-三数之和.md

tags, create time

tags	create time
LeetCode 双指针 中等	2026-05-13 16:00

06-三数之和

题面

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

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

• 3 <= nums.length <= 3000
• -10^5 <= nums[i] <= 10^5

---

思路

[!question] 💡 思考 如果题目是"两数之和等于 0"，我们会怎么做？排序后用双指针在两端相向收缩即可。但现在是三数之和，多了一个未知数——我们该如何把三维问题降成二维？

关键突破口：如果我们固定其中一个数，剩下的问题就等价于"两数之和等于某个目标值"，正好可以用双指针解决。

整体框架

[!info] 🎯 核心思想

1. 先排序 —— 去重的基础，也是双指针能工作的前提。
2. 枚举第一个数 nums[i]，然后对剩余部分用双指针找另外两个数，使三者之和为 0。
3. 跳过重复 —— 三层去重：外层跳过重复的 i，内层跳过重复的 left 和 right。

flowchart TD
    A["排序数组 nums"] --> B["for i 从 0 到 n-3"]
    B --> C{"nums[i] > 0?"}
    C -->|"是"| D["提前结束（最小值已正）"]
    C -->|"否"| E{"i > 0 且 nums[i] == nums[i-1]?"}
    E -->|"是"| F["continue（跳过重复 i）"]
    E -->|"否"| G["left = i+1, right = n-1"]
    G --> H{"left < right?"}
    H -->|"否"| B
    H -->|"是"| I["sum = nums[i]+nums[left]+nums[right]"]
    I --> J{"sum > 0?"}
    J -->|"是"| K["right--"]
    J -->|"否"| L{"sum < 0?"}
    L -->|"是"| M["left++"]
    L -->|"否"| N["记录三元组\n左指针右移去重\n右指针左移去重"]
    K --> H
    M --> H
    N --> H
    F --> B
    D --> O["返回结果"]

去重策略详解

这是本题最核心的难点。假设数组已排序，以下三个位置都需要处理重复：

[!abstract] 🔬 为什么排序后重复元素会聚集？

排序让相同的数字排在一起，这样当我们遍历过一个值之后，下一个相同值一定紧跟其后。通过检查前一个位置，我们可以直接跳过整个重复段，而不需要额外空间。

第一层：外层循环去重（固定点 i）

if i > 0 and nums[i] == nums[i-1]:
    continue  // 跳过重复的第一个数

[!question] ❓ 为什么 i > 0 才检查？ 因为 i = 0 时没有前驱元素，自然不需要去重。更重要的是——只有当 i > 0 时，nums[i-1] 已经作为固定点被完整枚举过一遍了，此时再用同样的值只会产生重复组合。

第二层：左指针去重（第二个数 left）

// 找到一组解后，left 右移并跳过所有重复值
left++
for left < right and nums[left] == nums[left-1]:
    left++

第三层：右指针去重（第三个数 right）

// 找到一组解后，right 左移并跳过所有重复值
right--
for left < right and nums[right] == nums[right+1]:
    right--

剪枝优化

排序后的数组可以带来重要的剪枝机会：

[!tip] ✂️ 两条剪枝规则

① 最小值剪枝：如果 nums[i] > 0，那么后面的所有数也都大于 0，三个正数之和不可能为 0 → 直接 break。

② 最大值剪枝：当前 nums[i] 与最大的两个数之和仍小于 0，说明 nums[i] 太小了，继续尝试也没有意义 → continue（注意是 continue，不是 break，因为后面更大的 i 可能可行）。

以 nums = [-4, -1, -1, 0, 1, 2] 为例，逐步展示去重过程：

i	nums[i]	left	right	sum	动作
0	-4	1	5	-4 + (-1) + 2 = -3	< 0，left++
0	-4	2	5	-4 + (-1) + 2 = -3	< 0，left++
0	-4	3	5	-4 + 0 + 2 = -2	< 0，left++
0	-4	4	5	-4 + 1 + 2 = -1	< 0，left++
0	-4	5	5	—	left >= right，进入下一轮 i
1	-1	2	5	-1 + (-1) + 2 = 0 ✅	记录 [-1,-1,2]，left 去重→3，right 去重→4
1	-1	3	4	-1 + 0 + 1 = 0 ✅	记录 [-1,0,1]，left 去重→4，right 去重→3
1	-1	4	3	—	left >= right，进入下一轮 i
2	-1	—	—	i > 0 && nums[2] == nums[1] → continue（跳过重复！）
3	0	4	5	0 + 1 + 2 = 3	> 0，right-- → 相遇，退出

最终结果：[[-1,-1,2], [-1,0,1]]

时间复杂度：O(n²) —— 外层循环 O(n)，内层双指针 O(n)，总体 O(n²)。 空间复杂度：O(log n) —— 排序的空间开销（取决于语言实现，Go 使用快速排序的递归栈）。

---

代码提示

// 伪代码模板
sort(nums)
result = []

for i from 0 to n-3:
    // 剪枝：最小值已经为正
    if nums[i] > 0:
        break
    
    // 去重：跳过重复的 i
    if i > 0 and nums[i] == nums[i-1]:
        continue
    
    left = i + 1
    right = n - 1
    target = -nums[i]  // 剩余两数之和应等于 -nums[i]
    
    for left < right:
        sum = nums[left] + nums[right]
        
        if sum == target:
            result.append([nums[i], nums[left], nums[right]])
            
            // 去重 left
            left++
            while left < right and nums[left] == nums[left-1]:
                left++
            
            // 去重 right
            right--
            while left < right and nums[right] == nums[right+1]:
                right--
                
        else if sum < target:
            left++  // 和太小，左指针右移增大
        else:
            right-- // 和太大，右指针左移减小

[!note] 🧠 目标值的转换 nums[i] + nums[left] + nums[right] == 0 等价于 nums[left] + nums[right] == -nums[i]。把三数之和问题转化为"在子数组中找两数之和等于一个固定目标值"，这就是典型的问题降维。

---

技巧

[!tip] 🔑 核心模式：排序 + 双指针（Sorted Two Pointers）

这是双指针中最经典的一类——「一固定，双滑动」：固定一个维度后，在剩余的有序区间上，左右指针根据大小关系各自向内收缩。这类模式的通用步骤：

1. 排序（前提条件，同时也是去重的基石）
2. 枚举第一个元素（可以是任意位置，常见的是从头到尾扫一遍）
3. 双指针在剩余区间查找
4. 去重：每层循环/搜索中都处理相等相邻元素

变体应用：四数之和（LeetCode 18）、最接近的三数之和（LeetCode 16）、三数最小的三元组之和（LeetCode 17）。

[!info] 🐹 Go 中的排序 Go 的标准库提供 slices.Sort() (Go 1.21+) 或 sort.Ints() (老版本)。排序后切片仍然是原切片的引用视图，不会创建副本。

import "slices"
slices.Sort(nums)

[!warning] ⚠️ 常见错误

① 去重放在错误的位置：先去重再移动指针会导致漏掉当前解。正确顺序是先记录结果，再去重移动。

② i 的范围错误：i 最多走到 n - 3，因为还需要至少两个元素给 left 和 right。

③ 忘记剪枝：如果不做 nums[i] > 0 的提前结束优化，虽然不影响正确性，但在面试中是一个加分项。

④ 内层去重用错比较对象：left 去重时应该和 nums[left-1] 比（刚走过的），right 去重时应该和 nums[right+1] 比（刚跳过的）。

[!summary] 📊 复杂度速查

方面	复杂度	说明
时间	O(n²)	排序 O(n log n) + 主逻辑 O(n²)
空间	O(log n)	排序递归栈
去重层数	3 层	i / left / right
剪枝条件	2 条	nums[i] > 0; nums[i] + nums[n-2] + nums[n-1] < 0

---

代码

func threeSum(nums []int) [][]int {
	slices.Sort(nums)
	n := len(nums)
	var result [][]int

	for i := 0; i < n-2; i++ {
		// 剪枝：最小值已大于 0，三个正数不可能和为 0
		if nums[i] > 0 {
			break
		}

		// 去重：跳过重复的第一个数
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}

		left, right := i+1, n-1
		target := -nums[i]

		for left < right {
			sum := nums[left] + nums[right]

			if sum == target {
				result = append(result, []int{nums[i], nums[left], nums[right]})

				// 去重：左指针跳过重复值
				left++
				for left < right && nums[left] == nums[left-1] {
					left++
				}

				// 去重：右指针跳过重复值
				right--
				for left < right && nums[right] == nums[right+1] {
					right--
				}
			} else if sum < target {
				left++ // 和太小，需要更大的数
			} else {
				right-- // 和太大，需要更小的数
			}
		}
	}

	return result
}

[!success] ✅ 运行验证

• LeetCode 第 15 题，通过率约 38%，中等难度中的高频面试题。
• 核心难点在于去重的正确处理，建议先在草稿纸上模拟排序后的数组走向，理解每一层去重的时机和边界条件。
• 这道题也可以看作是「两数之和」问题的升级版，掌握了双指针模板后，延伸到「k 数之和」也很自然——依次固定 k-2 个数，最后两层用双指针收尾。