Untitled

mail@pastecode.io avatar
unknown
python
2 years ago
913 B
3
Indexable
Never
def twoSum(arr, target):
    results = []
    seen = set()
    for x in arr:
        if target - x in seen:
            results.append((x, target - x, -target))
        
        seen.add(x)
    
    return results

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        results = []
        seen = set()
        for i in range(len(nums)):
            target = -nums[i]
            # why do we do this?
            # we can skip numbers we've already dealt with
            if target in seen:
                continue

            seen.add(target)

            res = twoSum(nums[i+1:], target)
            results.extend(res)

        # sort to ensure consistent hash
        #
        # why convert to a tuple?
        # tuples are hashable, lists are not
        results = [tuple(sorted(res)) for res in results]

        # dedup
        results = set(results)
        return results