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.

Implementation

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 Analysis

Time Complexity

O(n²)

Space Complexity

O(1)

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