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

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

brute force: calculate all possible sum of two numbers and compare with target sum O(n^2)

a. sort array, then use two pointers O(nlog(n) + n) // 这里不适用 因为我们要返回index

better way: O(n) space - HashMap

遍历array，假设当前的 num[i ] = a, 我们只需要查看map 中是否存在 b

if (b in map)： return map.get(b) and i // index in map is smaller than current i

else: 把当前visited value a and index i 放进 HashMap - < number, index>