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(n3)，在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(n2)。

算法步驟：

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(n2)

  • 排序：O(n log n)
  • 外層循環：O(n)
  • 內層雙指針：O(n)
  • 總體：O(n log n) + O(n2) = O(n2)

• 空間復雜度：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）

”`