作為 Leetcode 的第一題，兩數之和自然是知名度最高的，從兩數之和出發也有不少的衍生題目，下面就讓我們好好地解決它們。

1. 兩數之和

class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:record = dict()for i, num in enumerate(nums):if target - num in record:return [record[target - num], i]else:record[num] = i

最直接的思路是用哈希表，把出現過的數字（及其索引下標）都用哈希表記錄下來，這樣每當遍歷新的數字，就能快速找出 target - num 是否出現過，若是則返回下標。

170. 兩數之和 III - 數據結構設計

class TwoSum:def __init__(self):self.record = dict()def add(self, number: int) -> None:if number in self.record:self.record[number] += 1else:self.record[number] = 1def find(self, value: int) -> bool:for num in self.record.keys():if value - num != num:if value - num in self.record:return Trueelif self.record[num] > 1:return Truereturn False

這題是不斷地向數組添加數字，同時得能夠檢查數字是否為數組中某兩個數字之和，思路還是哈希表，每當要對數字進行檢查時，這個數字就相當于 target，遍歷數組中的數字 num，找到 target - num 是否也在數組中即可。要注意的是可能出現 target - num 等于 num 的情況，而這種情況得 num 出現過兩次才能返回 True，所以要用字典統計 num 出現的次數。

167. 兩數之和 II - 輸入有序數組

class Solution:def twoSum(self, numbers: List[int], target: int) -> List[int]:n = len(numbers)left = 0right = n - 1while left < right:total = numbers[left] + numbers[right]if total > target:right -= 1elif total < target:left += 1else:return [left+1, right+1]

相較于上一題，這題的條件是數組已經按非遞減順序排列，這其實也給了我們一個新的思路，因為有序數組總是與雙指針聯系在一起。所以說，這題我們可以使用左右雙指針 left 與 right，當兩數之和大于 target 時右指針左移，當兩數之和小于 target 時左指針右移，正好等于 target 時返回答案（注意下標從 1 開始）。

15. 三數之和

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:ans = []n = len(nums)nums.sort()for i in range(n):# 除了首位置之外，如果有多個重復的 nums[i]，那就只考慮最后一個if i > 0 and nums[i] == nums[i - 1]:continueleft = i + 1right = n - 1while left < right:total = nums[i] + nums[left] + nums[right]# total 太大，右指針左移if total > 0:right -= 1# total 太小，左指針右移elif total < 0:left += 1else:# total 符合條件ans.append([nums[i], nums[left], nums[right]])# 避免 left + 1 與 left 一樣while left < right and nums[left] == nums[left + 1]: left += 1# 避免 right - 1 與 right 一樣while left < right and nums[right] == nums[right - 1]: right -= 1# 確保了不會出現重復的答案left += 1right -= 1return ans

從上一題得到的靈感，就是可以將數組排序然后用雙指針解法，這對于三數、四數甚至更高的數之和都是適用的。在本題中，我們首先遍歷并固定第一個下標 i，然后對它后面的區域進行雙指針查找。由于不能出現重復的三元組，所以去重點有兩個：
1、除了第一個位置以外，凡是 nums[i] == nums[i-1] 的，就說明 i 這個位置的數與上一個位置的重復了，直接考慮 i + 1。如果用的是 nums[i] == nums[i+1] 判斷，就會把如 (-1, -1, 2) 這樣的答案給忽略掉。
2、每當找到一個答案以后，left 和 right 指針都要移動，而它們應該跳過與當前位置數字相同的位置，避免出現重復的三元組。

18. 四數之和

class Solution:def fourSum(self, nums: List[int], target: int) -> List[List[int]]:ans = []nums.sort()n = len(nums)for i in range(n):if i > 0 and nums[i] == nums[i-1]:continuefor j in range(i+1, n):if j > i+1 and nums[j] == nums[j-1]:continueleft = j + 1right = n - 1while left < right:total = nums[i] + nums[j] + nums[left] + nums[right]if total > target:right -= 1elif total < target:left += 1else:ans.append([nums[i], nums[j], 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 ans

與三數之和相比，僅僅是多遍歷了一個 j，注意 j 的位置是從 i + 1 開始的，所以它的去重是 if j > i+1 and nums[j] == nums[j-1]:

總結

以上是生活随笔為你收集整理的两数、三数、四数之和相关题目（Leetcode题解-Python语言）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。