leetcode中如何解决三数之和问题

# LeetCode中如何解决三数之和问题

## 问题描述

三数之和（3Sum）是LeetCode中一道经典的算法题（题目编号15），要求在一个整数数组中找到所有不重复的三元组`[nums[i], nums[j], nums[k]]`，使得`i != j != k`且`nums[i] + nums[j] + nums[k] = 0`。

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

解题思路分析

暴力解法（不推荐）

直接使用三重循环枚举所有可能的三元组，时间复杂度为O(n³)，在LeetCode上会超时。

def threeSum(nums):
    result = []
    n = len(nums)
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                if nums[i] + nums[j] + nums[k] == 0:
                    triplet = sorted([nums[i], nums[j], nums[k]])
                    if triplet not in result:
                        result.append(triplet)
    return result

排序+双指针法（最优解）

这是解决三数之和问题的标准解法，时间复杂度为O(n²)。

算法步骤：

1. 排序数组：首先将数组排序，这是后续去重和双指针操作的基础
2. 固定一个数：遍历数组，将当前元素作为第一个数
3. 双指针查找：使用左右指针在剩余数组中寻找另外两个数
4. 去重处理：跳过重复元素以避免重复解

详细解法实现

Python实现

def threeSum(nums):
    nums.sort()
    result = []
    n = len(nums)
    
    for i in range(n-2):
        # 跳过重复的起始值
        if i > 0 and nums[i] == nums[i-1]:
            continue
            
        left, right = i+1, n-1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                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 += 1
                right -= 1
    return result

Java实现

import java.util.*;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i-1]) continue;
            
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum < 0) {
                    left++;
                } else if (sum > 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;
    }
}

关键点解析

1. 排序的重要性：

   • 使重复元素相邻，便于去重
   • 使双指针法成为可能（基于有序数组的二分特性）

2. 去重处理：

   • 外层循环跳过与前一个相同的元素
   • 内层循环在找到解后跳过所有相同元素

3. 双指针移动规则：

   • 和小于0：左指针右移（增大和）
   • 和大于0：右指针左移（减小和）
   • 和等于0：记录结果并同时移动两个指针

复杂度分析

• 时间复杂度：O(n²)

  • 排序：O(n log n)
  • 外层循环：O(n)
  • 内层双指针：O(n)
  • 总体：O(n log n) + O(n²) = O(n²)

• 空间复杂度：O(1)或O(n)

  • 取决于排序算法的实现（Python的sorted()使用TimSort，空间复杂度为O(n)）

边界情况处理

1. 数组长度不足3：

   if len(nums) < 3:
      return []
   

2. 所有元素相同：

   • 如[0,0,0,0]应返回[[0,0,0]]

3. 无解情况：

   • 如[1,2,3]应返回空列表

常见错误与修正

1. 忘记排序：

   • 导致双指针法无法正确工作

2. 去重不彻底：

   • 只在外层循环去重而忽略内层循环的去重

3. 指针移动错误：

   • 找到解后只移动一个指针会导致遗漏或重复

扩展思考

四数之和问题

类似的解法可以扩展到4Sum问题，只需在外层再加一层循环：

def fourSum(nums, target):
    nums.sort()
    result = []
    n = len(nums)
    
    for i in range(n-3):
        if i > 0 and nums[i] == nums[i-1]:
            continue
        for j in range(i+1, n-2):
            if j > i+1 and nums[j] == nums[j-1]:
                continue
            left, right = j+1, n-1
            while left < right:
                total = nums[i] + nums[j] + nums[left] + nums[right]
                if total < target:
                    left += 1
                elif total > target:
                    right -= 1
                else:
                    result.append([nums[i], nums[j], 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 result

三数之和的变种

1. 最接近的三数之和（LeetCode 16）：

   • 找出和最接近目标值的三元组
   • 解法类似，但需要维护一个最小差值

2. 较小的三数之和（LeetCode 259）：

   • 统计满足和小于目标值的三元组数量

实际应用场景

1. 数据分析：在大量数据中寻找特定组合
2. 金融领域：组合投资分析
3. 游戏开发：物品组合效果计算

总结

三数之和问题是一个考察综合算法能力的经典题目，它融合了： - 排序算法的应用 - 双指针技巧 - 边界条件处理 - 去重逻辑

掌握这个问题的解法不仅可以帮助你通过面试，更能培养解决复杂问题的思维能力。建议在理解的基础上多次练习，并尝试解决其变种问题以加深理解。

练习题推荐

1. LeetCode 1. 两数之和（Two Sum）
2. LeetCode 16. 最接近的三数之和（3Sum Closest）
3. LeetCode 18. 四数之和（4Sum）
4. LeetCode 259. 较小的三数之和（3Sum Smaller）

”`