Two Sum

From LeetCode

problem description / solution in java

Solution in Python3

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        num_i = {}  # Number to index
        for i, v in enumerate(nums):
            complement = target - v
            if complement in num_i:
                return [num_i[complement], i]
            num_i[v] = i

I am lucky to get

Runtime: 40 ms, faster than 99.21% of Python3 online submissions for Two Sum.

Time Complexity

\(O(n)\), where \(n\) is the number of numbers.

Variants

Return numbers instead of their indices.

Store just numbers, use set instead of dict. sample

More than one pair

Make a collection of pairs. sample