LeetCode實踐之一 Two Sum

LeetCode實踐之一 Two Sum

題目描述：
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

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

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
可能出現的badcase: 答案中存在一個數為target/2時。
實現思路：若第一層遍歷數1，第二層遍歷數2，則時間復雜度O(n2)遍歷。若僅進行第一遍遍歷，在尋找第二個數的時候使用Hash表存儲數據，則時間復雜度為O(n)，此時需要注意badcase問題。

實現代碼如下：

class Solution {
public:
    vector twoSum(vector &numbers, int target) {
        map hash_map;
        vector r;
        for (int i=0; i != numbers.size(); ++i)
        {
            hash_map[numbers[i]] = i;
        }
        for(int i=0; i != numbers.size(); ++i)
        {
            map::iterator it = hash_map.find(target-numbers[i]);
            if (it != hash_map.end())
            {
                if(i+1 == it->second+1)
                    continue;
                r.push_back(min(i+1, it->second+1));
                r.push_back(max(i+1, it->second+1));
            }
        }
        return r;
    }
};