15. 3Sum

Problem

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

Discussion

An extended version of 1. Two Sum. Based on our result in Two Sum, we have a result of O(n) solution with two integer in the input, we can target a solution for this problem of O(n^2).

If we simply enhanced the solution based on Two Sum, we have to figure out the de-duplication step. And as the solution should be of O(n^2), we can try to sort the input array first.

And based on this, we can try to use a pointer approach to scan all the elements within each iteration.

Solution

Our solution begins with sorting the input list, then a loop iterating along the input list.

In each iteration, we will use a 2-pointer approach to scan all the pairs of elements.

As duplicate elements may appears and we want to avoid same combination, we will try to skip the first elements by skipping the element same with the previous one.

We will define the two pointers as the beginning and the end of the remaining sub list. Similarly we will update the first element if it's same as the previous one.

Then we simply evaluate the same of the three elements. If it is positive we will try to reduce it's value, then we update the last element with a smaller index, vice versa for negative value.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []

        for i in range(len(nums)):
            if i > 0 and nums[i - 1] == nums[i]:
                continue

            left, right = i + 1, len(nums) - 1

            while left < right:
                if left > i + 1 and nums[left - 1] == nums[left]:
                    left += 1
                    continue

                value = nums[i] + nums[left] + nums[right]

                if value > 0:
                    right -= 1

                elif value < 0:
                    left += 1

                else:
                    result.append([nums[i], nums[left], nums[right]])
                    left += 1
                    right -= 1

        return result

Complexity Analysis

• Time Complexity: O(n^2), as a double loop is implemented.
• Space Complexity: O(1), as only constant value is saved in memory.