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 的數值時就對其可能的重複情況進行考慮

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      

實作思路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 可能的重複情況進行考慮，確定最終結果中不會包含有重複的三元組

'''
學習中遇到問題沒人解答？小編建立了一個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