LeetCode 1. Two Sum

December 10, 2020

We can do a single pass through the input list, checking whether we've already seen (target - current value). We can store the seen values in a map from value to index so we know our return index pair.

This algorithm runs in $O(n)$ time and $O(n)$ space.

from typing import List
import unittest

class Test(unittest.TestCase):

    def setUp(self):
        self.s = Solution()

    def test_examples(self):
        self.assertEqual(self.s.twoSum([2,7,11,15], 9), [0,1])
        self.assertEqual(self.s.twoSum([3,2,4], 6), [1,2])
        self.assertEqual(self.s.twoSum([3,3], 6), [0,1])

class Solution:

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = {}
        for i in range(len(nums)):
            key = target-nums[i]
            if key in seen:
                return [seen[key], i]
            seen[nums[i]] = i

if __name__ == "__main__":
    unittest.main()