15.3Sum(Medium).md

15. 3Sum (Easy)

Date and Time: Jul 9, 2024, 16:25 (EST)

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

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.

Edge case:

Input: nums = [-1, 0, 1, -1, 0, 1]

Output: [ [-1, 0, 1] ]

Constraints:

• 3 <= nums.length <= 3000

• -10^5 <= nums[i] <= 10^5

KeyPoints:

We can reduce the 3Sum problem into Two Sum II Problem by sorting nums first, then start with the first entry in triplets by looping over nums, and set two pointers l, r by l = i + 1, r = len(nums)-1. Each time we calculate the curr by taking the sum of these three elements, and if curr < 0 we increment l because nums is sorted and we move l to the right to increment curr, the same case when curr > 0.

For the first if statement, we want to check there is no duplicate when we start with the first element. Look at Example 1, after nums.sort(), nums = [-4, -1, -1, 0, 1, 2], so when nums[1] = nums[2] = -1, we don't want to check nums[2], so we continue. Similar reasoning for Edge case, when nums = [-1, -1, 0, 0, 1, 1], if we don't skip when nums[l] = nums[l+1] = 0, we will have duplicate result that [[-1, 0, 1], [-1, 0, 1]].

My Solution:

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            l, r = i + 1, len(nums)-1
            while l < r:
                curr = nums[i] + nums[l] + nums[r]
                if curr < 0:
                    l += 1
                elif curr > 0:
                    r -= 1
                else:
                    res.append([nums[i], nums[l], nums[r]])
                    l += 1
                    while l < r and nums[l] == nums[l-1]:
                        l += 1
        return res

Time Complexity: $O(n^2)$
Space Complexity: $O(n)$