[LeetCode] 15. 3Sum

https://leetcode.com/problems/3sum/

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]]
Example 2:

Input: nums = []
Output: []
Example 3:

Input: nums = [0]
Output: []

Github Solution

#time: O(n^2), space: O(1)
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if not nums:
            return []
        nums = sorted(nums)
        ret = []
        for idx in range(len(nums)):
            if idx != 0 and nums[idx] == nums[idx-1]:
                continue
            target = 0 - nums[idx]
            left = idx+1
            right = len(nums)-1
            while left < right:
                if left != idx+1 and nums[left] == nums[left-1]:
                    left += 1
                    continue
                if right != len(nums)-1 and nums[right] == nums[right+1]:
                    right -= 1
                    continue
                if nums[left] + nums[right] < target:
                    left += 1
                elif nums[left] + nums[right] > target:
                    right -= 1
                else:
                    ret.append([nums[idx], nums[left], nums[right]])
                    left += 1
                    right -= 1
        return ret

Solution:

1. Sort first, and use the first pointer scan from left to right index。 After the first pointer point A number, we can transfer the problem to two sum questions. Target equal to 0-A. The problem requires not to contain duplicate triplets so we need to skip them.
2. We need to skip duplicate numbers pointed by the first pointer. Then using left_pointer = first+1 and right_pointer = lens(array)-1
3. left_pointer points to the next value if the sum of two pointers is smaller than the target value
4. right_pointer points to the last value if the sum of two pointers is larger than the target value
5. append the solutions to the result array if the sum of two pointers is equal to the target value. Then left_pointer++，right_pointer–
6. remind that left_pointer and right_pointer also have some chances to point duplicate numbers. We need to handle them as well.
7. We can also use a hash map for the two-sum sub-problem. However, it is better to use sort instead of a hash map when the question requires skipping duplicate triplets.

解法：

1. 先排序，從頭掃到尾，固定一個數後，讓target value 變成(0-此數)，就用剩下數組變成two sum來求出此target解，因為題目要求不能重複的解答，所以要跳過重複的組合。
2. 一開始固定的數就要跳過重複的數字。using low_pointer = first+1 and high_pointer = len(array)-1
3. 左和右兩個pointer所指的值相加，比target value小的時候，low_pointer++
4. 左和右兩個pointer所指的值相加，比target value大的時候，high_pointer–
5. 如果左和右兩個pointer所指的值相加，把值放到最後要return的數組裡，low_pointer++，high_pointer–
6. 注意low_pointer，high_pointer也會有重複的問題，記得要跳過跟前一個一樣的數
7. two sum的部分也可以用hashtable解，但如果有重複的元素，還是sorted用以上方法比較好解