Skip to content

15. 3Sum

Medium

Description

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.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]
Output: [[0, 0, 0]]
Explanation: The only possible triplet sums up to 0.

Constraints:

  • 3 <= nums.length <= 3000
  • -10โต <= nums[i] <= 10โต

Solutions ๐Ÿ”’

Approach: Sorting + Two Pointers (using HashSet)

Time complexity: \(O(n^2)\)

Space complexity: \(O(|ans|)\) = \(O(n)\)

Algorithm

First, sort the array to make it easier to skip duplicates and use the two-pointer technique.

Iterate through each element, treating it as the first element of the triplet.

For each element, use two pointers (one starting just after the current element and the other at the end of the array) to find pairs that sum to the negative of the current element.

Skip over duplicate elements to avoid duplicate triplets in the result.

Use a set to store the triplets to automatically handle duplicates.

Convert the set of tuples back to a list of lists before returning.

Sorting the array takes \(O(n \log n)\), and the two nested loops take \(O(n^2)\). Thus, the overall time complexity is dominated by the \(O(n^2)\) part.

The space complexity is \(O(n)\) due to the storage of the result in a set, which can contain up to \(O(n)\) unique triplets. No additional significant space is used.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ans = set()
        n = len(nums)
        nums = sorted(nums)
        for i in range(n):
            l,r = i+1,n-1
            while l<r:
                S = nums[i]+nums[l]+nums[r]
                if S == 0:
                    ans.add((nums[i],nums[l],nums[r]))
                    l+=1
                    r-=1
                elif S > 0:
                    r-=1
                else:
                    l+=1

        return [list(tup) for tup in ans]

Approach :Two Pointers +Sorting

Time complexity: \(O(n^2)\)

Space complexity: \(O(|ans|)\) = \(O(n)\)

Algorithm

We notice that the problem does not require us to return the triplet in order, so we might as well sort the array first, which makes it easy to skip duplicate elements.

Next, we enumerate the first element of the triplet \(nums[i]\) , where \(0 โ‰ค i< nโˆ’2\).

For each \(i\), we can find \(l\) and \(r\) satisfying \(nums[i]+nums[l]+nums[r]=0\) by maintaining two pointers \(l=i+1\) and \(r=nโˆ’1\).

In the enumeration process, we need to skip duplicate elements to avoid duplicate triplets.

The specific judgment logic is as follows:

If \(i>0\) and \(nums[i]=nums[iโˆ’1]\), it means that the element currently enumerated is the same as the previous element, we can skip it directly, because it will not produce new results.

If \(nums[i] > 0\), it means that the element currently enumerated is greater than \(0\), so the sum of three numbers must not be equal to \(0\), and the enumeration ends.

Otherwise, we let the left pointer \(j=i+1\), and the right pointer \(k=nโˆ’1\).

When \(l < r\), the loop is executed, and the sum of three numbers \(summ = nums[i]+nums[l]+nums[r]\) is calculated and compared with \(0\):

  • If \(summ < 0\), it means that \(nums[l]\) is too small, we need to move \(l\) to the right.
  • If \(summ > 0\), it means that \(nums[r]\) is too large, we need to move \(r\) to the left.
  • Otherwise, it means that we have found a valid triplet, add it to the answer \(ans\), move \(l\) to the right, move \(r\) to the left, and skip all duplicate elements to continue looking for the next valid triplet.

After the enumeration is over, we can get the answer \(ans\) to the triplet.

The time complexity is \(O(n^2)\) and the space complexity is \(O(\log n)\). The \(n\) is the length of the array.

class Solution:
    def threeSum(self,nums:List[int])->List[List[int]]:
        if len(nums) < 3: return ans

        nums = sorted(nums)
        ans = []
        n = len(nums)
        for i in range(n-2):
            if i>0 and nums[i]==nums[i-1]:
                continue
            # Choose nums[i] as the first number in the triplet, then search the
            # remaining numbers in [i + 1, n - 1].
            l , r = i+1,n-1
            while l < r:
                summ = nums[i]+nums[l]+nums[r]
                if summ==0:
                    ans.append((nums[i],nums[l],nums[r]))
                    l+=1
                    r-=1
                    #skip duplicates
                    while nums[l]==nums[l-1] and l<r:
                        l+=1
                    while nums[r]==nums[r+1] and l<r:
                        r-=1

                elif summ <0:
                    l+=1
                else:
                    r-=1

        return ans
Akhil Singh Chauhan Akhil Singh Chauhan
Creator

Comments