LeetCode 15：三数之和
题目描述
难度：中等
给定一个整数数组 nums，找出所有满足以下条件的三元组：
- 三个元素来自不同的数组下标。
- 三个元素之和等于
0。 - 答案中不能包含重复的三元组。
示例 1
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2
输入：nums = [0,1,1]
输出：[]
示例 3
输入：nums = [0,0,0]
输出：[[0,0,0]]
题解
思路：排序与双指针
先对数组进行升序排序。排序后固定第一个数 nums[i]，再使用左右指针在区间 [i+1, n-1] 中寻找另外两个数。
left指向固定值右侧的第一个候选位置。right指向数组末尾。- 三数之和小于
0时，移动left可以让和增大。 - 三数之和大于
0时，移动right可以让和减小。 - 三数之和等于
0时，记录结果，并移动两个指针继续查找。
数组有序后，当 nums[i] > 0 时，当前值及其右侧元素都大于 0，已经无法组成和为 0 的三元组，可以提前结束遍历。
去重
题目要求结果中不能出现重复三元组，因此需要在三个位置上处理重复值：
- 固定第一个数时，如果
nums[i] == nums[i-1]，跳过当前值。 - 找到一个答案后，移动
left，并跳过与前一个左侧值相同的元素。 - 同时移动
right，并跳过与前一个右侧值相同的元素。
例如排序后的数组为 [-4,-1,-1,0,1,2]。第一个 -1 已经完成搜索后，第二个 -1 无需再次作为固定值，从而避免生成相同的三元组。
正确性说明
固定 nums[i] 后，问题转化为在右侧有序区间中寻找两个数，使它们的和等于 -nums[i]。
当三数之和偏小时，右指针左侧的值不会让结果增大，移动左指针可以排除当前最小候选值；当三数之和偏大时，移动右指针可以排除当前最大候选值。每次移动都会安全地缩小搜索区间，所有满足条件的组合都能被找到。
三处去重会跳过数值相同且搜索范围等价的情况，因此最终结果中的三元组互不重复。
复杂度分析
- 时间复杂度：
O(n²)。排序需要O(n log n)，外层遍历与内层双指针搜索共需要O(n²)，整体由O(n²)主导。 - 空间复杂度：
O(log n)。Go 标准库排序使用原地排序，递归过程需要栈空间；这里不计算返回结果占用的空间。
Go 代码
import "slices"
func threeSum(nums []int) [][]int {
slices.Sort(nums)
n := len(nums)
ans := [][]int{}
for i, num := range nums[:n-2] {
if num > 0 {
break
}
if i > 0 && num == nums[i-1] {
continue
}
l, r := i+1, n-1
for l < r {
sum := num + nums[l] + nums[r]
if sum > 0 {
r--
} else if sum < 0 {
l++
} else {
ans = append(ans, []int{num, nums[l], nums[r]})
for l++; l < r && nums[l] == nums[l-1]; l++ {
}
for r--; r > l && nums[r] == nums[r+1]; r-- {
}
}
}
}
return ans
}
slices.Sort(nums) 会改变传入数组的元素顺序，并要求使用 Go 1.21 或更高版本。如果调用方还需要原始顺序，可以先复制数组，再对副本进行排序。
小结
排序为双指针提供了明确的移动方向，将枚举三个元素的 O(n³) 解法优化到 O(n²)。这道题还需要同步处理固定值和左右指针的重复元素，才能保证答案唯一。