LeetCode（1）Two Sum

題目：

Given an array of integers, find two numbers such that they add up to a specific target number.

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

分析：

該題目標記為Medium，難度為中等，閱讀題目後，第一反應便是兩次遍歷數組，些許判斷便可解決。然後三下五除二寫下了代碼，信心滿滿提交：

class Solution
{
public:
    vector twoSum(vector &numbers , int target)
    {
        vector index;
        for(int i=0 ; i!=numbers.size(); i++)
        {
            for(int j=numbers.size()-1 ; j>i; j--)
                if((numbers[i]+numbers[j]) == target)
                {
                    index.push_back(i+1);
                    index.push_back(j+1);
                    break;
                }

        }//for
        return index;
    }//twoSum
};

沒錯，想嘛，堂堂LeetCode中等難度的題目，就這樣可以AC的話豈不是。。。於是，我就得到了這樣的回應： Status:

Time Limit Exceeded

 

再次分析：

重新審視題目，上面提供的O(n^2)的算法肯定達不到要求，到底應該用什麼方式可以避免重疊循環，思來想去還是沒有答案，最終還是只能求助百度了。當掃到一網友的分析後，恍然大悟，我們學習哈希干嘛的呀，就是因為它有著與生俱來的復雜度的優勢。 廢話不多說，下面提供AC代碼：

class Solution
{
public:
    vector twoSum(vector &numbers , int target)
    {
        vector index;
        map hashMap;
        for(unsigned int i=0 ; i
這樣，算法復雜度就降到了O(n)，順利AC了我的第一個LeetCode題目。
看來，自己還是水到家了，還需要繼續努力！
測試main函數：

為了方便程序測試，這兒也提供main函數的代碼，供於參考：
int main()
{
    Solution s;
    int arr[3] = {3,2,4};
    int target = 6;
    vector numbers(arr , arr+3);
    vector index;
    index = s.twoSum(numbers , target);

    cout<<"index1="<