前言

大家好，我是毛毛。ヾ(´∀ ˋ)ﾉ
那就開始今天的解題吧~

Question

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.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

Constraints:

• 3 <= nums.length <= 3000
• -10^5 <= nums[i] <= 10^5

Think

給一個陣列nums，找出三個元素且總和為0的所有可能性。

而且相同組合不同排列視為一樣的，不重覆計算~

其實這個跟Two Sum的解法差不多，我們先固定第一個index，接著當成在解Two Sum一樣，從左右兩側逼近，直到原來左邊的index大於原來右邊的index，表示這一Round找完了，讓第一個index+1，重複以上的動作~

Code

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums) <= 2:
            return []
        elif len(nums) == 3:
            if sum(nums) != 0:
                return []
            else:
                return [nums]
        nums = sorted(nums)
        #  0  1  2  3  4  5  #
        # -4 -1 -1  0  1  2
        # print("nums: ", nums, "\n")
        
        index1 = 0
        index2 = 1
        index3 = len(nums)-1
        
        ans = []
        
        while index1 != len(nums)-2:
            
            # print("index1: ", index1, ", index2: ", index2, ", index3: ", index3)
            total = nums[index1] + nums[index2] + nums[index3]
            # print("value: ", total)
            if total == 0:
                # print("OK: ", nums[index1], nums[index2], nums[index3])
                if [nums[index1], nums[index2], nums[index3]] not in ans:
                    # print("Insert list\n")
                    ans.append([nums[index1], nums[index2], nums[index3]])
                index2 += 1
                index3 -= 1
                
                if index2 > index3-1:
                    # print("Got 0, index2 cross index3 =>", index2, ":", index3, "\n")
                    index1 += 1
                    index2 = index1 + 1
                    index3 = len(nums) - 1
            else:
                if index1 == len(nums)-3 and index2 == len(nums)-2 and index3 == len(nums)-1:
                    # print("Should break: ", index1, index2, index3)
                    break

                if index2 >= index3-1:
                    # print("index2 beside index3 =>", index2, ":", index3, "\n")
                    index1 += 1
                    index2 = index1 + 1
                    index3 = len(nums) - 1

                elif total < 0:
                    # print("Too small, index2 add\n")
                    index2 += 1

                elif total > 0:
                    # print("Too big, index3 substract\n")
                    index3 -= 1
                
            
        return ans

Submission

今天就到這邊啦~
大家明天見