--- tags: ["LeetCode", "双指针", "中等"] create time: 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`。 ```mermaid 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()` (老版本)。排序后切片仍然是原切片的引用视图，不会创建副本。 > ```go > 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 | --- ## 代码 ```go 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 个数，最后两层用双指针收尾。