Skip to main content

3Sum

Question​

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.

Example 1
Input: nums = [-1, 0, 1, 2, -1, -4]

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

Solution​

all//3Sum.py
def threeSum(nums):
    res = [] # store the results
    nums.sort() # sort the list
    for i in range(len(nums)-2): # loop through the list, starting from the first element
        # check if the current element is duplicate to the last element, if duplicate, skip to next element
        if i > 0 and nums[i] == nums[i-1]:
            continue
        # two pointer, one from the current element, one from the last element
        l, r = i+1, len(nums)-1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s < 0: # if the sum is less than 0, move the left pointer to the next element
                l +=1
            elif s > 0: # if the sum is greater than 0, move the right pointer to the previous element
                r -= 1
            else:
                res.append((nums[i], nums[l], nums[r])) # if the sum is 0, add the triplet to the result
                # check if the left or right pointer is duplicate, if duplicate, move the pointer to the next/previous element
                while l < r and nums[l] == nums[l+1]:
                    l += 1
                while l < r and nums[r] == nums[r-1]:
                    r -= 1
                l += 1; r -= 1
    return res

nums = [-1, 0, 1, 2, -1, -4]
result = threeSum(nums)
#print(result)
result
[(-1, -1, 2), (-1, 0, 1)]