1

這題看起來滿直觀的，感覺只要設兩個for迴圈，跑過所有可能的組合就好，但實際把下面這段程式碼放進去跑會發現time limit exceed。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;

        for(int i=0; i<nums.size(); i++)
        {
            for(int j=i+1; j<nums.size(); j++)
            {
                if(nums[i]+nums[j] == target)
                {
                    ans.push_back(i);
                    ans.push_back(j);
                }
            }
        }

        return ans;
    }
};

所以看起來應該是要做一些優化。因為之前不知道從哪邊聽到這題可以用Hash Table來輔助，所以就嘗試往這個方向想看看。直觀來想，如果剛剛跑兩層迴圈會超過時間，那現在的優化應該就是只能跑一次迴圈，並將過程中的一些訊息記錄在Hash Table。再往下發想，就會聯想到可能是跑到nums[i]時，要儲存target-nums[i]跟他對應到的i，例如我有個例子是:

nums = [2, 7, 11, 15]
target = 9

如果我在跑到2的時候就先儲存(2, 0)，這樣我在迴圈跑到7的時候，就會發現9-7已經在Hash Table裡，然後就可以取得2的index了。有了這個想法之後，就可以實作出下列的程式碼:(發現對map不太熟，順手記錄一下一個好連結)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        map<int, int> indexMap;
        map<int, int>::iterator iter;

        for(int i=0; i<nums.size(); i++)
        {
            iter = indexMap.find(target-nums[i]);
            if(iter != indexMap.end())
            {
                ans.push_back(iter->second);
                ans.push_back(i);
                return ans;
            }
            else 
            {
                indexMap.insert(pair<int, int>(nums[i], i));
            }
        }

        return ans;
    }
};

Java版本

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        /*
        use a hashmap to save pair of (nums[i],i)
        for each element in nums,
            if target-nums[i] exist in map,
                return (map.get(target-nums[i] ), i)
            else
                put(nums[i],i) into map
        return new int[];
        */
        int[] ans = new int[2];
        if(nums.length ==0) return ans;
        Map<Integer, Integer> map = new HashMap<>();
        for(int i=0; i<nums.length; i++){
            if(map.containsKey(target-nums[i])){
                ans[0]=map.get(target-nums[i]);
                ans[1]=i;
                return ans;
            }else{
                map.put(nums[i],i);
            }
        }
        return ans;
    }
}