LeetCode 熱題100 | 15. 三數(shù)之和

大家好，今天我們來(lái)解決一道經(jīng)典的算法題——三數(shù)之和。這道題在 LeetCode 上被標(biāo)記為中等難度，要求我們從一個(gè)整數(shù)數(shù)組中找到所有不重復(fù)的三元組，使得三元組的和為 0。下面我將詳細(xì)講解解題思路，并附上 Python 代碼實(shí)現(xiàn)。

題目描述

給定一個(gè)整數(shù)數(shù)組 nums，判斷是否存在三元組 [nums[i], nums[j], nums[k]] 滿足 i != j、i != k 且 j != k，同時(shí)還滿足 nums[i] + nums[j] + nums[k] == 0。請(qǐng)你返回所有和為 0 且不重復(fù)的三元組。

示例：

輸入：nums = [-1,0,1,2,-1,-4]
輸出：[[-1,-1,2],[-1,0,1]]

解題思路

這道題的核心是找到所有滿足條件的三元組，同時(shí)避免重復(fù)。我們可以通過(guò)排序數(shù)組和雙指針?lè)▉?lái)高效地解決這個(gè)問(wèn)題。

核心思想

1. 排序數(shù)組：

   • 將數(shù)組排序，方便后續(xù)使用雙指針?lè)ā?/li>

2. 遍歷數(shù)組：

   • 固定一個(gè)數(shù) nums[i]，然后在剩下的數(shù)組中使用雙指針?lè)▽ふ覂蓚€(gè)數(shù) nums[left] 和 nums[right]，使得 nums[i] + nums[left] + nums[right] == 0。

3. 雙指針?lè)?/strong>：

   • 初始化 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，則找到一個(gè)三元組，記錄下來(lái)，并跳過(guò)重復(fù)的元素。

4. 去重：

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

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

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

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

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