Swift｜三數之和（3Sum）詳細題解 + 注釋 + 拓展（LeetCode 15）

?題目描述

給你一個包含 n 個整數的數組 nums，判斷 nums 中是否存在三個元素 a, b, c，使得 a + b + c = 0。請你找出所有和為 0 且不重復的三元組。

注意：答案中不能包含重復的三元組。

---

🧠解題思路

本題是 LeetCode 中非常經典的“雙指針”+“去重”問題，屬于中等難度。

? 步驟如下：

1. 對數組進行排序：便于后續去重處理和雙指針的使用。
2. 固定一個數 nums[i]：枚舉 i，并為其設置兩個指針 left（i+1）和 right（nums.count - 1）。
3. 使用雙指針向中間靠攏，判斷三數之和是否為 0。
4. 去重操作：
   • 對 i 進行去重，跳過與前一個數相同的情況。
   • 對 left 和 right 也要去重，防止重復三元組。

---

🧾 Swift 代碼實現（含詳細注釋）

func threeSum(_ nums: [Int]) -> [[Int]] {let nums = nums.sorted()  // 排序是關鍵，便于去重和雙指針var result: [[Int]] = []for i in 0..<nums.count - 2 {// 如果當前數字和前一個數字相同，跳過，避免重復三元組if i > 0 && nums[i] == nums[i - 1] {continue}var left = i + 1var right = nums.count - 1while left < right {let sum = nums[i] + nums[left] + nums[right]if sum == 0 {// 找到一個有效三元組result.append([nums[i], nums[left], nums[right]])// 去重：移動 left 指針跳過相同的數while left < right && nums[left] == nums[left + 1] {left += 1}// 去重：移動 right 指針跳過相同的數while left < right && nums[right] == nums[right - 1] {right -= 1}left += 1right -= 1} else if sum < 0 {// 總和偏小，左指針右移以增大總和left += 1} else {// 總和偏大，右指針左移以減小總和right -= 1}}}return result
}

---

??時間復雜度分析

步驟	復雜度
排序	O(nlogn)
遍歷 + 雙指針查找	O(n^2)
總體時間復雜度	O(n2)

• n 是數組的長度。
• 最壞情況下，每個元素都要與后面的所有元素進行組合查找。

🧠空間復雜度

• 使用了常數級別的輔助空間（除了結果數組）：O(1)。
• 如果考慮返回結果的空間，那么是 O(k)，其中 k 為結果中三元組的個數。

---

🔍輸入輸出示例

let nums = [-1, 0, 1, 2, -1, -4]
print(threeSum(nums)) 
// 輸出： [[-1, -1, 2], [-1, 0, 1]]

---

🧱邊界情況說明

輸入	輸出	說明
[]	[]	空數組
[0, 0, 0]	[[0,0,0]]	需要處理重復值
[1, 2, -2, -1]	[]	沒有滿足條件的組合

---

🧩拓展與優化

1. 如果要求和為 target 而非 0：

   • 將判斷條件 sum == 0 改為 sum == target 即可。
   • 本題可以推廣為 kSum 問題（如 Two Sum、Four Sum）。

2. 去重邏輯處理建議封裝為函數：

   • 提高代碼可讀性與復用性。

3. Swift 中使用 Set 存儲結果避免重復：

   • 如果輸入較多或存在重復項較多，可以考慮用 Set<[Int]> 先去重再轉成 [[Int]]。

---

🏁總結

• 本題考察的是數組排序 + 雙指針技巧。
• 核心是合理處理重復元素，避免重復解。
• 時間復雜度為 O(n2)，在面試中屬于經典問題，建議掌握。

---

如果你覺得有用，歡迎點贊、評論支持我繼續更新 💪
你也可以在評論區分享你遇到的變體，我來幫你一起解答！