今天是紀錄LeetCode解題的第十五天

第十五題題目：Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.

給定一個整數數組，傳回所有滿足nums[i] + nums[j] + nums[k] = 0且i != j != k的所有組合
請注意，傳回數組不能包含重複的組合

解題思路

這題我們用雙指針解，定義i=0~len(nums)-2(假設有五項，i在第三項，那麼l會等於第四項，r等於第五項，所以i的範圍不用到最後一項就可以找出所有符合的組合)、l = i + 1、r = len(nums) - 1，這裡的i在每一次while迴圈中為固定值，移動l、r雙指針去找出目前nums[i]有沒有符合題目其餘兩個數nums[l]跟nums[r]

程式碼

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []       
        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i-1]:
                continue  #避免重複   
            l, r = i + 1, len(nums) - 1 
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if s == 0:
                    result.append([nums[i], nums[l], nums[r]])
                    l += 1
                    r -= 1
                    #跳過重複值
                    while l < r and nums[l] == nums[l-1]:
                        l += 1
                    while l < r and nums[r] == nums[r+1]:
                        r -= 1
                elif s < 0:
                    l += 1
                else:
                    r -= 1                   
        return result

跳過重複值的地方概念是一樣的，因為我們操作的是排序過後的數組，範例1的nums = [-1,0,1,2,-1,-4]，排序後nums = [-4,-1,-1,0,1,2]，我們要避免i或l或r會剛好等於nums[2]的位置，這樣才不會重複找到以-1為主的組合(nums[1]時就已經找過)，l和r也是一樣，避免有重複到的指針

執行過程

初始狀態

• nums = [-1,0,1,2,-1,-4]
• 排序後：nums = [-4,-1,-1,0,1,2]
• result = []

第一次執行(i = 0)

• l = i + 1 = 1
• r = len(nums) - 1 = 6 - 1 = 5
• s = nums[0] + nums[1] + nums[5] = -4 + -1 + 2 = -3
• s < 0 → l += 1 → l = 2

• s = nums[0] + nums[2] + nums[5] = -4 + -1 + 2 = -3
• s < 0 → l += 1 → l = 3

• s = nums[0] + nums[3] + nums[5] = -4 + 0 + 2 = -2
• s < 0 → l += 1 → l = 4

• s = nums[0] + nums[4] + nums[5] = -4 + 1 + 2 = -1
• s < 0 → l += 1 → l = 5
• l = r = 5，離開while迴圈，表示-4沒有辦法找出符合的組合

第二次執行(i = 1)

• l = i + 1 = 2
• r = len(nums) - 1 = 6 - 1 = 5
• s = nums[1] + nums[2] + nums[5] = -1 + -1 + 2 = 0
• s = 0 → result.append([nums[1] + nums[2] + nums[5]]) → result = [[-1,-1,2]]
• l += 1 → l = 3
• r -= 1 → r = 4

• s = nums[1] + nums[3] + nums[4] = -1 + 0 + 1 = 0
• s = 0 → result.append([nums[1] + nums[3] + nums[4]]) → result = [[-1,-1,2],[-1,0,1]]
• l += 1 → l = 4
• r -= 1 → r = 3
• l > r，離開while迴圈，表示i = 1為主的元素已找完所有組合

第三次執行(i = 2)

• i > 0 and nums[i] == nums[i-1] → i > 0 and nums[2] == nums[1] == -1 → continue (以-1為主的組合已經找完，所以不用重複再尋找一次)

第四次執行(i = 3)

• l = i + 1 = 4
• r = len(nums) - 1 = 6 - 1 = 5
• s = nums[3] + nums[4] + nums[5] = 0 + 1 + 2 = 3
• s > 0 → r -= 1 → r = 4
• l = r = 4，離開while迴圈，表示0沒有辦法找出符合的組合或已經找完組合

最後回傳result = [[-1,-1,2],[-1,0,1]]就是答案了，這題要注意i、l、r都要判斷是否有重複的可能性，不然可能會多找到幾組重複的組合