0015. 3Sum - chasel2361/leetcode GitHub Wiki

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0?
Find all unique triplets in the array which gives the sum of zero.
The solution set must not contain duplicate triplets.

Given array nums = [-1, 0, 1, 2, -1, -4], A solution set is:
  [[-1, 0, 1],
   [-1, -1, 2]]

最一開始的想法是直接硬幹，把list排序之後，只要湊出三個相加為零的值就挑出來存著

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        ans = []
        for i in range(n):
            for j in range(i+1, n):
                for k in range(j+1, n):
                    num = [nums[i], nums[j], nums[k]]
                    if sum(num) == 0:
                        num.sort()
                        if not num in ans:
                            ans.append(num)
        return ans

這樣的做法雖然可行，但時間複雜度是O(N^3)太高了，不被系統接受，所以開始參考別人的寫法。

首先是medium上大大的解，但無法理解的是，為何認定-v-x一定會出現在給定的list裡

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums) < 3:
            return []
        nums.sort()
        res = set()
        for i, v in enumerate(nums[:-2]):
            if i >= 1 and v == nums[i-1]:
                continue
            d = {}
            for x in nums[i+1:]:
                if x not in d:
                    d[-v-x] = 1
                else:
                    res.add((v, -v-x, x))
        return list(res)

因為有無法理解的地方，所以又去研究了其他人的做法，這次的做法是標準的two pointers，

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        n = len(nums)        
        for i in range(n-2): # [1]
            if nums[i] > 0: break # [2]
            if i>0 and nums[i] == nums[i-1]: continue # [3]
            
            left = i + 1
            right = n - 1 # [4]
            
            while left < right:
                total = nums[i] + nums[left] + nums[right]
                    
                if total > 0:
                    right -= 1 # [5]
                elif total < 0:
                    left += 1 # [6]
                else:
                    res.append([nums[i], nums[left], nums[right]]) # [7]
                        
                    while left < right and nums[left+1] == nums[left]: # [8]
                        left += 1
                    while left < right and nums[right-1] == nums[right]: # [8]
                        right -= 1                    
                    left += 1
                    right -= 1
        return res

[1] 從左取出i，但因為總共要取三個數，所以i只取至倒數第三個
[2] 因為i是由左至右取出，如果i代表的數字大於零，總和必大於等於零，此時也不必再搜尋了。
[3] 為了避免重複項，當i不為第零項時需檢驗其與下一項代表的數是否相同，若是則跳過當前項。
[4] 剩下兩個數為left及right，left從i+1起由左至右，right從末項起由右至左。
[5] 若總和大於零，需要把right往左移(減少總和)
[6] 若總和小於零則必須將left往右移
[7] 若等於零則表示取到答案。
[8]與i同樣，為了避免重複項，需要檢驗left、right與次項代表的數是否相同，若相同必須往次項移動

這樣寫的時間複雜度是O(N**2)，空間複雜度是O(1)

Code Link