目標：
這題主要目的在於練習HashMap/Dictionary的應用。

原題：

Question:
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, and you may not use the same element twice.

Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

分析/解題：
題目要求是，在一組陣列中找出兩個數，其加總恰等於給定值。
每個數不能被重複使用，且必剛好只有一個解。
像這種題目，由於被擺在第一題，大多數狀況都不會被拿來考XD
但，凡事總有例外。
我們先來分析一下，如果按照原題的要求該怎麼解。
如果input長度為N，那麼暴力解就是將數字兩兩相加看是不是解，
這樣的解法要算N(N-1)/2次，也就是O(N²)的時間複雜度。

該怎麼降低複雜度呢？我們會希望每個數只要查一次就知道結果，
有沒有這樣的結構？當然有，在Java中可以用HashMap，
而在Python中可以用dictionary。

只要每一次從map中確認當下target-num是否在map中，
在的話就表示找到了，可以將結果取得，
沒找到的話，就將一組(num, index)放進map中，
依此流程，最壞的狀況整個array遍歷後，就可以得到答案。

時間複雜度：
由於HashMap在put和get最好的狀況都是O(1)，
遍歷整個Map需要O(N)。

Java:

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i};
            }
            map.put(nums[i], i);              
        }
        throw new IllegalArgumentException("No Answer");
    }
}

Python:

class Solution:
    def twoSum(self, nums: 'List[int]', target: 'int') -> 'List[int]':
        numMap = {}
        for i in range(len(nums)):
            if numMap.__contains__(target-nums[i]):
                return [numMap.get(target-nums[i]), i]
            else:
                numMap[nums[i]] = i

面試實際可能會遇到的問題：
這裡有一個原則：
不論是什麼問題，不論你當下想到的方法有多暴力有多爛，
有想到方法就先講沒關係。
以這題為例，你應該先提出最先的O(N²)解，大概描述完以後，
再說但這樣時間複雜度比較高，
如果應用HashMap(python用dict)的話，
可以讓每個數只需要花O(1)作搜尋，複雜度就會降到O(N)。

先講出一個可能的解法，再想辦法延伸修改或者改進它，
這是大多數公司建議(尤其Google)的方式，
一來可以讓面試官知道你不是腦袋空空，至少先有個基本分，
二來在講這個暴力解時，你可以有緩衝的時間去想更好的解法。

還有一些需要注意的東西可以做為你和面試官互動和溝通的部分，
或有可能是面試官問你的進一步問題，
在平常每題解完後，都應該留點時間給自己去思考一下可能的變化。
以此題為例：
「請問這個陣列是否是排序好的？」(排好的解法就又不同了XD)
「如果我想要的是回傳那兩個數字而非indices的話呢？」(修改pair即可)
「你剛剛提到了排序，那怎樣的狀況先對陣列作排序會比較好？」
「如果答案存在很多組，能否找出所有的解？」
「如果當中存在重覆的數字的話呢？」
「為什麼HashTable/HashMap的存取是O(1)？」(這可能就扯比較遠了XD)
「那麼它們的worst case呢？什麼狀況下會發生？」

從LeetCode學演算法，我們下次見囉，掰~