Leetcode-threesum

Leetcode 15. 3Sum 解題心得

題目: 15. 3Sum

題目描述

給定一組整數陣列 nums，請找出所有不重複的三元組合，使得三元組合的總和為 0。

大概像這樣：

Given array nums = [-1, 0, 1, 2, -1, -4],

Answer:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

解題思路

可以用三個指針，然後分別去指向陣列中的每一個元素，然後再去找剩下的兩個元素，使得三個元素的總和為 0。

這邊要注意的是，因為題目要求不重複的三元組合，所以我們要先對陣列做排序，這樣才能避免重複的組合。

Code

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

1. 先對陣列做排序，這樣才能避免重複的組合，同時也方便 7 與 3 中的判斷。
2. 這邊的 len(nums) - 2 是因為我們用了3個指標，所以最後兩個元素不用再去找了。
3. 如果 nums[i] > 0，則代表 nums[i] 之後的元素都會大於 0，所以不可能有三元組合的總和為 0，所以可以直接 break。
4. 如果 i > 0 且 nums[i] == nums[i-1]，則代表 nums[i] 與 nums[i-1] 重複，所以可以直接 continue，因為不計算重複的組合。
5. l 與 r 分別指向 nums[i] 之後的第一個元素與最後一個元素。
6. 當 l < r 時，代表還有元素可以去找。
7. 如果 total < 0，則代表 nums[l] 需要更大一點，所以 l += 1，反之 r -= 1。
8. 如果 nums[l] 與 nums[r] 與 triplet 中的元素重複，則代表這個組合已經找過了，所以可以直接 l += 1 與 r -= 1，因為不計算重複的組合。