題目:

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.

給定一個陣列,回傳所有陣列中取三數相加為0的可能,且不能包含重複的可能
ex:input:[-1,0,1,2,-1,-4]=>output:[[-1,-1,2],[-1,0,1]]
explanation:
nums[0] + nums[1] + nums[1] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.

只要將其中一值固定,就相當於在找2sum

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ans=[]
        s=set()
        nums=sorted(nums)
        
        for i in range(len(nums)):
            if nums[i]>0: #若固定值為正就不用再找三和為0的可能
                break

            if nums[i] not in s:
                l=i+1
                r=len(nums)-1
                target=-nums[i] #兩數相加要等於負的固定值
                while l<r:
                    if nums[l]+nums[r]>target:
                        r=r-1
                    elif nums[l]+nums[r]<target:
                        l=l+1
                    else:
                        ans.append([nums[i],nums[l],nums[r]])
                        l=l+1
                        while l<r and nums[l-1]==nums[l]: #不斷移動直到值變得不一樣為止
                            l=l+1         
                s.add(nums[i]) #紀錄考慮過的固定值
        
        return ans

先將陣列排序,方便後續操作,ans紀錄要回傳的可能性
從頭開始,輪流將該位值當作固定值
而我們在固定值右側的數列找出我們要和固定值互補的兩個值
我有做幾個加快效率的處理:
1.不考慮左側因為這樣會考慮重複的可能(先前就考慮過了)
2.若固定值為正就不用再找三和為0的可能了,因為右側都是正數(陣列被排序過)
3.我們也有用set(s)來記錄已經當過固定值的數,若固定值已經在set內就不用再次去考慮它的可能性

確定固定值後,接下來是找另外兩個互補值的部分:
設立兩個指標(l,r)分別放在右側數列的兩端

若固定值+nums[l]+nums[r]小於0,則l往後走
讓nums[l]變更大好讓三數和等於0(陣列被排序過)

若固定值+nums[l]+nums[r]大於0,則r往前走
讓nums[r]變更小好讓三數和等於0(陣列被排序過)

若固定值+nums[l]+nums[r]等於0,紀錄這個可能到ans
接著移動l或r都可以(我這邊選擇移動l),但為了不要紀錄到重覆的可能
需要不斷移動直到值變得不一樣為止

重複上述操作直到l和r碰面,再找下一個固定值

全部執行完後回傳ans所記錄的可能即可
最後執行時間760ms(faster than 91.03%)

那我們下題見