O(n)

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        d = {}

        for i, e in enumerate(nums):
            if (target-e) in d:
                return [d[target-e], i]
            if e not in d:
                d[e] = i

def main():
    s = Solution()

    print(s.twoSum([2, 7, 11, 15], 9)) 

if __name__ == '__main__':
    main()