15. 3Sum

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        seen = set()
        ans = []
        
        for i in range(len(nums)-2):
            j, k = i+1, len(nums)-1
            target = -nums[i]
            
            while j < k:
                s = nums[j] + nums[k]
                if s == target and (nums[i], nums[j], nums[k]) not in seen:
                    ans.append([nums[i], nums[j], nums[k]])
                    seen.add((nums[i], nums[j], nums[k]))
                    j += 1
                    k -= 1
                elif s > target:
                    k -= 1
                else:
                    j += 1
        
        return ans

• we sort the array, and for each value, we can use two pointers on the rest of the array to hone in from either side for three numbers that sum to zero.

Categories:: sorting, two-pointers, array