MediumLeetCode #15Two Pointers

3Sum

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.

Constraints

3 <= nums.length <= 3000, -10^5 <= nums[i] <= 10^5

Examples

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

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

Solution

Approach

Sort the array. Fix one element and use two pointers on the remaining array to find pairs that sum to the negative of the fixed element.

def threeSum(nums):
    nums.sort()
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]:
            continue
        left, right = i + 1, len(nums) - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left+1]:
                    left += 1
                while left < right and nums[right] == nums[right-1]:
                    right -= 1
                left += 1
                right -= 1
    return result

Complexity

Time:O(n²)

Space:O(1)

Hints

1.Sort the array first
2.Fix one number and use two pointers for the other two
3.Skip duplicates to avoid duplicate triplets

Asked at

Google