Leetcode: Two Sum

Two Sum | LeetCode OJ

To find indices of numbers that add to a given target we can use the following approach

1. Iterate over list using enumerate to get both the index and the number
2. Store index of each number and check if the difference between target and current number exist in the dictionary

Remark:

1. O(n) time complexity for iterating over the list
2. O(n) space complexity for using a dictionary

Extensions:

1. Handle case when the solution does not exist in the list
2. Return all pairs that satisfies the property

The second function implements the extensions

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        d = {}
        for i, num in enumerate(nums):
            if target - num in d:
                return d[target - num], i
            d[num] = i
def twoSum(self, nums, target):
        res, d = [], {}
        for i, num in enumerate(nums):
            if target - num in d:
                res.append((d[target - num], i))
            d[num] = i
        return res