Medium

3Sum

036

Return all unique triplets that sum to zero. Return triplets and the outer list in ascending lexicographic order.

EXAMPLES

Example 1

Input
{
  "nums": [
    -1,
    0,
    1,
    2,
    -1,
    -4
  ]
}

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

FUNCTION SHAPE

nums: intArray→intMatrix

SOLUTION NOTE

The classic problem similar to Two Sum. The trick is handling duplicates - we don't want any duplicates in output.

For two sum: if nums[i] + nums[j] == target, append to res, then skip all consecutive nums[i] on the left and all consecutive nums[j] on the right. For a given (i,j) that sums to target, there is no other possible matching value for index i other than nums[j].

Reveal reference solution +

pythonREFERENCE

def threeSum(self, nums: List[int]) -> List[List[int]]:
    nums.sort()
    n = len(nums)
    res = []

    def twoSum(start, end, target):
        pairs = []
        i, j = start, end
        while i < j:
            if nums[i] + nums[j] == target:
                pairs.append([nums[i], nums[j]])
                while i + 1 < j and nums[i] == nums[i + 1]:  # skip dups
                    i += 1
                while j - 1 > i and nums[j] == nums[j - 1]:  # skip dups
                    j -= 1
                i += 1
                j -= 1
            elif nums[i] + nums[j] > target:
                j -= 1
            else:
                i += 1
        return pairs

    i = 0
    while i < n:
        pairs = twoSum(0, i - 1, -nums[i])
        for p in pairs:
            res.append(p + [nums[i]])

        while i + 1 < n and nums[i] == nums[i + 1]:  # skip dups
            i += 1
        i += 1

    return res

TimeO(n²)

SpaceO(1)

Open on LeetCode ↗