Problem Statement in English

You’re given an integer array nums and an integer target. Return all the unique triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == target.

Approach

We can solve this problem using the two-pointer technique. The idea is to sort the array and then use two pointers to find the pairs that sum up to the target.

So we iterate through the array and for each element, we use two pointers to find the pairs that sum up to the target.

In the 2 pointer part, if we find a pair that sums up to the target, we add it to the result and move both pointers – the left pointer to the right and the right pointer to the left. If the sum is less than the target, we move the left pointer to the right. If the sum is greater than the target, we move the right pointer to the left.

And we’re done!

Solution in Python


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

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

            l, r = i + 1, len(nums) - 1

            while l < r:
                s = nums[i] + nums[l] + nums[r]

                if s > 0:
                    r -= 1
                elif s < 0:
                    l += 1
                else:
                    res.append((nums[i],nums[l],nums[r]))
                    l += 1
                    while l < r and nums[l - 1] == nums[l]:
                        l += 1

        return res

Complexity

  • Time: $O(n^2)$
    Since we have a nested loop, the outer loop runs n times and the inner loop runs n times in the worst case. Therefore, the time complexity is $O(n^2)$.

  • Space: $O(1)$
    Since we are not using any extra space, the space complexity is $O(1)$.

And we are done.