15. 3Sum

Medium

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.

Solution

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

        for i in range(n):
            j, k = i + 1, n - 1
            while j < k:
                potential = nums[i] + nums[j] + nums[k]
                if potential == 0:
                    res.add((nums[i], nums[j], nums[k]))
                    j += 1
                elif potential < 0:
                    j += 1
                else:
                    k -= 1

        return list(res)