Two Sum - Leetcode

Today I'm going to go over three solutions to the popular leetcode question Two Sum.

The question is this: given an array of numbers and a target number, return the indices of two numbers that add up to the target number.

Solutions:

1. O(n^2) time, O(1) space We can use two for loops to loop through the array and find the indices of the two numbers that add up to the target number.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

1. O(n) time, O(n) space We can use a hash table to store the numbers as keys and the indices as values. Then we check to see if the difference (target - number) is in the hash table. If it is, return both the index of the number and the index of the difference.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        values = {}
        for i, num in enumerate(nums):
            diff = target - num
            if diff in values:
                return [i, values[diff]]
            values[num] = i
        return []

1. O(nlogn) time, O(1) space You can use the two pointer method. After sorting the array and creating an array of the numbers and their indices, create two pointers i and j where i = 0 and j = len(array)-1. If the sum is smaller than target, increment i, if larger, increment j. If equal, return the indices.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        i = 0
        j = len(nums) - 1
        sortedNums = sorted(zip(nums, range(len(nums))))
        while i < j:
            if sortedNums[i][0] + sortedNums[j][0] == target:
                return [sortedNums[i][1], sortedNums[j][1]]
            elif sortedNums[i][0] + sortedNums[j][0] < target:
                i += 1
            elif sortedNums[i][0] + sortedNums[j][0] > target:
                j -= 1