15-3Sum.md

15. 3Sum

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.

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: []

Constraints:

• 0 <= nums.length <= 3000
• -105 <= nums[i] <= 105

Solution

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        ans = []
        for left in range(0, len(nums) - 2):
            if left == 0 or nums[left] != nums[left-1]:
                mid = left + 1
                right = len(nums) - 1
                while mid < right:
                    if nums[left] + nums[mid] + nums[right] == 0:
                        ans.append([nums[left], nums[mid], nums[right]])
                        while mid < right and nums[mid+1] == nums[mid]:
                            mid += 1
                        while mid < right and nums[right-1] == nums[right]:
                            right -= 1
                        mid += 1
                        right -= 1
                    elif nums[left] + nums[mid] + nums[right] > 0:
                        right -= 1
                    else:
                        mid += 1
        return ans

Traverse all possible values for left and use two pointer model on mid and right: O(n²).