Three Sum

Solution 1

The idea of the solution is:

1) Iterate over every elements

2) Apply a Two Sum with target equal minus the current element and the array being all other elements

3) The Two Sum returns all the pairs that sum to minus the current element

4) Cast the pairs in triplets by adding the current element and add them to the list of all triplets

5) Return the list of all triplets

def threeSum(nums: List[int]) -> List[List[int]]:
    # helper is a two sum where the kth element can't be used
    def helper(nums, target, k):
        d = dict()

        for i in range(len(nums)):
            if i != k:
                d[target-nums[i]] = i

        # already_seen is used to not add more than once the same triple of number
        out, already_seen = [], set()
        for i in range(len(nums)):
            if nums[i] not in already_seen and i != k and nums[i] in d and i != d[nums[i]] and nums[i] <= target - nums[i]:
                out.append(tuple(sorted([nums[k], nums[i], nums[d[nums[i]]]])))
                already_seen.add(nums[i])
        return(out)

    # already_seen is used to not add more than once the same triple of number
    list_triplet_values, already_seen = list(), set()

    # iterate over the number and then call a twoSums on the other elements with target: -element
    for i in range(len(nums)):
        if nums[i] not in already_seen:
            list_triplet_values.extend(helper(nums, -nums[i], i))
            already_seen.add(nums[i])

    return(list(set(list_triplet_values)))

Solution 2

The idea is:

1) Sort the list of nums

2) Iterate with i over each element until len(nums)-2

3) Create two pointers: left starting at i+1 and right starting at len(num)-1 (last element)

4) Compute the sum of nums[i] + nums[left] + nums[right]

a) if the sum is smaller than 0 hence move left pointer by +1 (try a bigger number for the sum to be 0)

b) if the sum is greater than 0 hence move right pointer by -1 (try a smaller number for the sum to be 0)

c) otherwise add the triplet nums[i], nums[left], nums[right] to the list of valid sums

d) Move left and right to their next different number

5) Return the list of all valid triplets

def threeSum(nums: List[int]) -> List[List[int]]:
    list_triplet_values = []
    nums.sort() # sort the array to take advantage of this sort
    
    for i in range(len(nums)-2):
        # if the current number is the same as the previous one just continue (we want unique triplets)
        if i > 0 and nums[i] == nums[i-1]:
            continue
            
        # define left and right pointers
        left, right = i+1, len(nums)-1
        while left < right:
            sums = nums[i] + nums[left] + nums[right]
            # if the sum is smaller than 0 add 1 to left pointer to try with a bigger number
            if sums < 0:
                left +=1
            # if the sum is greater than 0 substract 1 to right pointer to try with a smaller number
            elif sums > 0:
                right -= 1
            # otherwise the triplet is valide
            else:
                list_triplet_values.append((nums[i], nums[left], nums[right]))
                
                # move left and right to the next different number
                while left < right and nums[left] == nums[left+1]:
                    left += 1
                while left < right and nums[right] == nums[right-1]:
                    right -= 1
                left, right = left + 1, right - 1
    return list_triplet_values