LeetCode 熱題100 | 15. 三數之和

大家好，今天我們來解決一道經典的算法題——三數之和。這道題在 LeetCode 上被標記為中等難度，要求我們從一個整數數組中找到所有不重復的三元組，使得三元組的和為 0。下面我將詳細講解解題思路，并附上 Python 代碼實現。

---

題目描述

給定一個整數數組 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]]

---

解題思路

這道題的核心是找到所有滿足條件的三元組，同時避免重復。我們可以通過排序數組和雙指針法來高效地解決這個問題。

核心思想

1. 排序數組：

   • 將數組排序，方便后續使用雙指針法。

2. 遍歷數組：

   • 固定一個數 nums[i]，然后在剩下的數組中使用雙指針法尋找兩個數 nums[left] 和 nums[right]，使得 nums[i] + nums[left] + nums[right] == 0。

3. 雙指針法：

   • 初始化 left = i + 1，right = len(nums) - 1。
   • 如果 nums[i] + nums[left] + nums[right] < 0，則 left 右移。
   • 如果 nums[i] + nums[left] + nums[right] > 0，則 right 左移。
   • 如果 nums[i] + nums[left] + nums[right] == 0，則找到一個三元組，記錄下來，并跳過重復的元素。

4. 去重：

   • 在遍歷過程中，跳過重復的 nums[i]、nums[left] 和 nums[right]，避免重復的三元組。

---

代碼實現

def threeSum(nums):""":type nums: List[int]:rtype: List[List[int]]"""nums.sort()  # 排序數組result = []  # 存儲結果for i in range(len(nums) - 2):  # 遍歷數組，固定 nums[i]if i > 0 and nums[i] == nums[i - 1]:  # 跳過重復的 nums[i]continueleft, right = i + 1, len(nums) - 1  # 初始化雙指針while left < right:total = nums[i] + nums[left] + nums[right]  # 計算三數之和if total < 0:left += 1  # 和小于 0，左指針右移elif total > 0:right -= 1  # 和大于 0，右指針左移else:result.append([nums[i], nums[left], nums[right]])  # 找到一個三元組# 跳過重復的 nums[left] 和 nums[right]while left < right and nums[left] == nums[left + 1]:left += 1while left < right and nums[right] == nums[right - 1]:right -= 1left += 1right -= 1return result

---

代碼解析

1. 排序數組：

   • 將數組排序，方便后續使用雙指針法。

2. 遍歷數組：

   • 固定一個數 nums[i]，然后在剩下的數組中使用雙指針法尋找兩個數 nums[left] 和 nums[right]。

3. 雙指針法：

   • 初始化 left = i + 1，right = len(nums) - 1。
   • 根據三數之和的大小，移動 left 或 right 指針。

4. 去重：

   • 在遍歷過程中，跳過重復的 nums[i]、nums[left] 和 nums[right]，避免重復的三元組。

---

復雜度分析

• 時間復雜度：O(n2)，其中 n 是數組的長度。排序的時間復雜度為 O(n log n)，雙指針法的時間復雜度為 O(n2)。
• 空間復雜度：O(1)，只使用了常數個額外空間。

---

示例運行

示例 1

# 輸入：nums = [-1,0,1,2,-1,-4]
nums = [-1, 0, 1, 2, -1, -4]
print(threeSum(nums))  # 輸出: [[-1, -1, 2], [-1, 0, 1]]

示例 2

# 輸入：nums = [0,1,1]
nums = [0, 1, 1]
print(threeSum(nums))  # 輸出: []

示例 3

# 輸入：nums = [0,0,0]
nums = [0, 0, 0]
print(threeSum(nums))  # 輸出: [[0, 0, 0]]

---

總結

通過排序數組和雙指針法，我們可以高效地找到所有滿足條件的三元組，并避免重復。這種方法的時間復雜度為 O(n2)，能夠處理較大的輸入規模。希望這篇題解對你有幫助！如果還有其他問題，歡迎繼續提問！

關注我，獲取更多算法題解和編程技巧！