Two Sum

https://leetcode.com/problems/two-sum/

| 2 | 7 | 11 | 15 |

　↑　　↑ 全てのコンビネーションを確認しようと Brute Force で問題を解こうとすると ループの中でループをするのでo(n^2)となる。

| 2 | 7 | 11 | 15 |

そのため HashMapを使う必要がある。 ループして array の中を確認する際に、 HashMap に val と key を持たせる。 ループ時に target - val の値が HashMap にあれば、 合計の値を持つ index が return できる。

| 2 | 7 | 11 | 15 |

  ↑

| HashMap |

| val : index | | 2 : 1 |

| HashMap |

| val : index | | 2 : 1 | | 7 : 2 |← | 11 : 3 | | 15 : 4 |

target は 9 なので val 7 を確認時に HashMap にすでに 2 が入っているので この時点で return できる。

一度だけのループなので、 Time complexity: O(n) Mem complexity: O(n) となる。

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        map = {}
        for i, n in enumerate(nums):
            diff = target - n
            if diff in map:
                return [map[diff], i]
            map[n] = i