LeetCode 15.三数之和是一道经典的数组操作题目，要求找出数组中所有和为0且不重复的三元组。题目难度为中等，但实际解决起来有不少细节需要注意。
题目描述如下：给定一个整数数组 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]]
这道题的难点在于如何高效地找到所有符合条件的三元组，同时避免重复结果。如果使用暴力解法，三重循环的时间复杂度为O(n³)，对于n=3000的输入规模来说会超时。因此我们需要更高效的算法。
解题思路
排序 + 双指针法
最优解法是使用排序 + 双指针的组合，将时间复杂度优化到O(n²)。基本思路如下：
先对数组进行排序，这样可以方便后续去重和使用双指针
固定第一个数nums[i]，然后使用双指针在i+1到n-1范围内寻找另外两个数
双指针分别为left=i+1和right=n-1，通过调整指针位置来寻找和为-nums[i]的两个数
注意去重操作，避免出现重复的三元组
为什么排序很重要？排序后：
相同的元素会相邻，便于去重操作
可以通过比较三数之和与0的关系来移动指针
可以提前终止不可能的搜索
算法步骤详解
排序数组：对输入数组进行排序，时间复杂度O(n log n)
遍历第一个数：
固定第一个数nums[i]，如果nums[i] > 0，由于数组已排序，后面不可能有三数之和为0，可以直接返回结果
如果nums[i]与前一个数相同，跳过以避免重复结果
双指针寻找另外两个数：
左指针left = i + 1，右指针right = n - 1
计算三数之和sum = nums[i] + nums[left] + nums[right]
如果sum > 0，右指针左移；如果sum < 0，左指针右移；如果sum == 0，记录结果
找到符合条件的三元组后，需要跳过相同的元素以避免重复
去重操作：
对第一个数去重：如果nums[i] == nums[i-1]，跳过
对第二个数去重：找到符合条件的三元组后，如果nums[left] == nums[left+1]，left++
对第三个数去重：找到符合条件的三元组后，如果nums[right] == nums[right-1]，right--
关键难点解析
去重逻辑：这是本题最容易出错的地方。需要注意的是，去重操作应该在找到一个有效三元组之后进行，而不是之前。否则可能会漏掉一些有效的三元组。
指针移动：找到有效三元组后，需要同时移动左右指针，并进行去重操作。
边界条件：需要注意数组越界问题，特别是在去重操作时。
代码实现
Python实现
class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:# 对数组进行排序nums.sort()result =n = len(nums)# 遍历第一个数for i in range(n - 2):# 如果第一个数大于0，后面不可能有三数之和为0if nums[i] > 0:break# 去重：跳过相同的第一个数if i > 0 and nums[i] == nums[i-1]:continue# 双指针初始化left, right = i + 1, n - 1while left < right:total = nums[i] + nums[left] + nums[right]if total < 0:left += 1elif total > 0:right -= 1else:# 找到符合条件的三元组result.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 += 1right -= 1return result
Java实现
import java.util.ArrayList;import java.util.Arrays;import java.util.List;class Solution {public List<List<Integer>> threeSum(int[] nums) {// 对数组进行排序Arrays.sort(nums);List<List<Integer>> result = new ArrayList<>();int n = nums.length;// 遍历第一个数for (int i = 0; i < n - 2; i++) {// 如果第一个数大于0，后面不可能有三数之和为0if (nums[i] > 0) {break;}// 去重：跳过相同的第一个数if (i > 0 && nums[i] == nums[i - 1]) {continue;}// 双指针初始化int left = i + 1, right = n - 1;while (left < right) {int total = nums[i] + nums[left] + nums[right];if (total < 0) {left++;} else if (total > 0) {right--;} else {// 找到符合条件的三元组result.add(Arrays.asList(nums[i], nums[left], nums[right]));// 去重：跳过相同的第二个数while (left < right && nums[left] == nums[left + 1]) {left++;}// 去重：跳过相同的第三个数while (left < right && nums[right] == nums[right - 1]) {right--;}// 移动双指针left++;right--;}}}return result;}}
Go实现
import "sort"func threeSum(nums []int) [][]int {// 对数组进行排序sort.Ints(nums)result := [][]int{}n := len(nums)// 遍历第一个数for i := 0; i < n - 2; i++ {// 如果第一个数大于0，后面不可能有三数之和为0if nums[i] > 0 {break}// 去重：跳过相同的第一个数if i > 0 && nums[i] == nums[i-1] {continue}// 双指针初始化left, right := i + 1, n - 1for left < right {total := nums[i] + nums[left] + nums[right]if total < 0 {left++} else if total > 0 {right--} else {// 找到符合条件的三元组result = append(result, []int{nums[i], nums[left], nums[right]})// 去重：跳过相同的第二个数for left < right && nums[left] == nums[left+1] {left++}// 去重：跳过相同的第三个数for left < right && nums[right] == nums[right-1] {right--}// 移动双指针left++right--}}}return result}
Rust实现
use std::collections::HashSet;impl Solution {pub fn three_sum(nums: Vec<i32>) -> Vec<Vec<i32>> {let mut nums = nums;// 对数组进行排序nums.sort();let mut result = Vec::new();let n = nums.len();// 遍历第一个数for i in 0..n {// 确保至少有三个元素if i + 2 >= n {break;}// 如果第一个数大于0，后面不可能有三数之和为0if nums[i] > 0 {break;}// 去重：跳过相同的第一个数if i > 0 && nums[i] == nums[i-1] {continue;}// 双指针初始化let mut left = i + 1;let mut right = n - 1;while left < right {let total = nums[i] + nums[left] + nums[right];if total < 0 {left += 1;} else if total > 0 {right -= 1;} else {// 找到符合条件的三元组result.push(vec![nums[i], nums[left], nums[right]]);// 去重：跳过相同的第二个数while left < right && nums[left] == nums[left+1] {left += 1;}// 去重：跳过相同的第三个数while left < right && nums[right] == nums[right-1] {right -= 1;}// 移动双指针left += 1;right -= 1;}}}result}}
C++实现
using namespace std;class Solution {public:vector<vector<int>> threeSum(vector<int>& nums) {// 对数组进行排序sort(nums.begin(), nums.end());vector<vector<int>> result;int n = nums.size();// 遍历第一个数for (int i = 0; i < n - 2; i++) {// 如果第一个数大于0，后面不可能有三数之和为0if (nums[i] > 0) {break;}// 去重：跳过相同的第一个数if (i > 0 && nums[i] == nums[i-1]) {continue;}// 双指针初始化int left = i + 1, right = n - 1;while (left < right) {int total = nums[i] + nums[left] + nums[right];if (total < 0) {left++;} else if (total > 0) {right--;} else {// 找到符合条件的三元组result.push_back({nums[i], nums[left], nums[right]});// 去重：跳过相同的第二个数while (left < right && nums[left] == nums[left+1]) {left++;}// 去重：跳过相同的第三个数while (left < right && nums[right] == nums[right-1]) {right--;}// 移动双指针left++;right--;}}}return result;}};
复杂度分析
时间复杂度
排序的时间复杂度：O(n log n)
双指针遍历的时间复杂度：O(n²)
总体时间复杂度：O(n²)，其中n是数组的长度
空间复杂度
O(log n) 到 O(n)，主要取决于排序算法使用的额外空间
如果不算存储结果的空间，算法本身只使用了常数级别的额外空间
拓展思考
相关问题
三数之和的变体：
最接近的三数之和（LeetCode 16）
四数之和（LeetCode 18）
三数之和小于K（类似问题）
去重技巧：
除了排序后跳过相同元素，还可以使用哈希集合来存储结果，自动去重
但哈希集合的方法会使用更多空间，且在某些情况下效率不如排序去重
优化技巧：
可以增加一些剪枝条件，如如果nums[i] + nums[i+1] + nums[i+2] > 0，直接break
如果nums[i] + nums[n-1] + nums[n-2] < 0，直接continue
实际应用场景
三数之和问题虽然是一个算法题，但其中蕴含的双指针技巧和去重思想在实际开发中也有应用：
数据分析：在数据集中寻找满足特定条件的组合
金融领域：寻找投资组合使得收益或风险达到特定目标
搜索优化：在有序数据中高效查找特定和的组合
常见错误与注意事项
去重时机：必须在找到一个有效三元组后再进行去重操作，否则可能漏掉解
边界条件：注意数组越界问题，特别是在处理去重时
指针移动：找到有效三元组后，需要同时移动左右指针
排序影响：排序会改变原数组顺序，但题目不要求返回原始索引，因此是允许的
总结
LeetCode 15.三数之和是一道经典的数组操作题目，通过排序+双指针的方法可以将时间复杂度优化到O(n²)。解决这道题的关键在于理解双指针的移动逻辑和去重操作。
本文详细解析了题目的解题思路，提供了五种编程语言的实现代码，并对时间和空间复杂度进行了分析。同时，还探讨了相关的拓展问题和实际应用场景。
掌握这道题目的解题技巧，不仅能帮助我们更好地理解双指针算法，还能为解决更复杂的n数之和问题打下基础。希望本文能帮助不同层次的读者深入理解三数之和问题的解法。