3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Tags: Array

Try It!

Discussion

Video

Solution

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

        for i in range(len(nums) - 2):
            if i == 0 or nums[i] != nums[i - 1]:
                self.two_sum(nums, i, ans)
        
        return ans

    def two_sum(self, nums, i, ans):
        target = -nums[i]
        j = i + 1
        k = len(nums) - 1
        while j < k:
            if nums[j] + nums[k] < target:
                j += 1
            elif nums[j] + nums[k] > target:
                k -= 1
            else:
                ans.append([nums[i], nums[j], nums[k]])

                while j < k and nums[j] == nums[j + 1]:
                    j += 1
                while j < k and nums[k] == nums[k - 1]:
                    k -= 1
                j += 1
                k -= 1