Python練習題：實現三數之和

題目

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

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

例如：

給定一個列表：[-1, 0, 1, 2, -1, -4]
返回結果：[(-1, -1, 2), (-1, 0, 1)]
給定一個列表：[1, 2, 4]
返回結果：[]
給定一個列表：[-1, 0, 1, 2, -1, -4, 0, 2, 0, 4, -4, -2, -1, 2]
返回結果：[(-4, 0, 4), (-4, 2, 2), (-2, 0, 2), (-1, -1, 2), (-1, 0, 1), (0, 0, 0)]

實現思路1

• 使用兩層循環，第一層循環確定第一個數 a 的數值，第二層循環確定第二個數 b 的數值，然後第三個數 c = 0 - a - b ，我們只需判斷 c 是否在列表中出現即可
• 根據上面的思路，我們實現起來並不難，但請注意本題有一個要求：不可以包含重復的三元組，所以我們就需要進行去重處理，而這個去重的細節過程也正是本題的一大難點
• 去重處理時，可以先找到所有符合條件的三元組，放到一個列表中，然後再去重，但這樣的去重處理可能不太好弄，所以我們可以在確定 a、b、c 的數值時就對其可能的重復情況進行考慮

代碼實現1

def threeSum(nums):
res = []
nums.sort() # 排序
for i in range(len(nums)):
if nums[i] > 0: # 排序後，如果第一個數 a 大於 0 ，那麼必然不存在符合條件的三元組
break
if i > 0 and nums[i] == nums[i - 1]: # 第一個數 a 去重
continue
tmp_set = set()
for j in range(i + 1, len(nums)):
# 從 j > i + 2 考慮，是因為允許有2種特殊情況: (1) a = b = c = 0; (2) a為負數，b = c 且 a + b + c = 0
if j > i + 2 and nums[j] == nums[j - 1] and nums[j] == nums[j - 2]: # 第二個數 b 去重
continue
a, b, c = nums[i], nums[j], 0 - nums[i] - nums[j]
if c in tmp_set:
res.append((a, b, c))
tmp_set.remove(c) # 第三個數 c 去重
else:
tmp_set.add(nums[j])
return res

實現思路2

• 使用 雙指針 的方法來實現
• 首先需要對 nums 按從小到大進行排序
• 第一層循環，同樣是確定第一個數 a 的數值，並且在這裡就對 a 可能的重復情況進行處理
• 接著定義兩個指針：left、right，分別表示第二個數 b 和第三個數 c 的下標，left初始位置定義在 a 的下一個位置，right的初始位置定義在 nums 最後一個數的位置
• 如果 a + b + c < 0，因為 nums 是排好序的，此時小於0，那麼就說明 b 的數值太小了，需要讓 b 增加，也就是 left 向右移動
• 如果 a + b + c > 0，因為 nums 是排好序的，此時大於0，那麼就說明 c 的數值太大了，需要讓 c 減小，也就是 right 向左移動
• 如果 a + b + c = 0，那麼就說明當前三元組符合條件，把該三元組添加到最終結果中
• 添加符合條件的三元組後，同樣需要對 b、c 可能的重復情況進行考慮，確保最終結果中不會包含有重復的三元組

代碼實現2

''' 學習中遇到問題沒人解答？小編創建了一個Python學習交流群：711312441 尋找有志同道合的小伙伴，互幫互助,群裡還有不錯的視頻學習教程和PDF電子書！ '''
def threeSum(nums):
res = []
nums.sort() # 排序
for i in range(len(nums)):
if nums[i] > 0: # 排序後，如果第一個數 a 大於 0 ，那麼必然不存在符合條件的三元組
break
if i > 0 and nums[i] == nums[i - 1]: # 第一個數 a 去重
continue
left, right = i + 1, len(nums) - 1
while left < right:
a, b, c = nums[i], nums[left], nums[right]
if a + b + c < 0: # nums是排好序的，此時小於0，那麼需要讓 b 增加，left向右移動
left += 1
elif a + b + c > 0: # nums是排好序的，此時大於0，那麼需要讓 c 減小，right向左移動
right -= 1
else:
res.append((a, b, c))
# a 在外層循環固定保持不變，所以找到一組符合條件的 b 和 c 後，left、right都需要移動
left += 1 # left向右移動
right -= 1 # right向左移動
while left < right and nums[left - 1] == nums[left]: # 第二個數 b 去重
left += 1
while left < right and nums[right] == nums[right + 1]: # 第三個數 c 去重
right -= 1
return res