leetcode 151 - 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

做了這題才發現不只邏輯要訓練，程式也要訓練
很直覺想用兩層for loop迴圈做掉這題
class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        vector<int> rvector(2), pvector(0);
        int i, j;
        for (i=0; i<numbers.size(); i++)
        {
            if (numbers[i] < target)
                pvector.push_back(numbers[i]);
        }

        for (i=0; i<pvector.size(); i++)
        {
            for (j=i+1; j<pvector.size(); j++)
            {
                if (pvector[i]+pvector[j] == target)
                {
                    rvector[0] = i+1;
                    rvector[1] = j+1;
                }
            }
        }

        return rvector;
    }
}; 
結果測試程式丟了個超長的內容來檢測
給出了 Time Limit Exceeded
所以看來是會要求執行效率
虧我還特地把不可能的數字先排除掉了(第一個迴圈)
所以用了個 array 來模擬個 hashtable(時間要快就是用空間換是很直覺的想法)
class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        vector<int> rvector(2), pvector(0);
        int i, j;
        int array[50000];

        for (i=0; i<50000; i++)
            array[i] = 0;

        for (i=0; i<numbers.size(); i++)
        {
            if (numbers[i] < target)
                pvector.push_back(numbers[i]);
        }
       
        for (i=0; i<pvector.size(); i++)
        {
            if (array[target-pvector[i]])
            {
                rvector[0] = array[target-pvector[i]];
                rvector[1] = i+1;
            }
            else
            {
                array[pvector[i]] = i+1;
            }
        }

        return rvector;
    }
};
結果測試程式丟出了負數的內容來檢測
跑出 Runtime Error 有夠賤
想一想要用陣列做出有負數的處理麻煩
且我原來排除不可能的數也因為出現負數導致不能這樣處理了

查過後才知道 C++ 裏面有一個 unordered 可以用
把 code 改成
class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        vector<int> rvector(2);
        int i;
        unordered_map<int, int> hashtable;

        for (i=0; i<numbers.size(); i++)
        {
            if (hashtable.count(target-numbers[i]))
            {
                rvector[0] = hashtable[target-numbers[i]];
                rvector[1] = i+1;
            }
            else
            {
                hashtable[numbers[i]] = i+1;
            }
        }

        return rvector;
    }
};
我 C++真的很不熟，一直都是寫純C或是php
這次就順便把一些 C++ 可以用的語法慢慢學起來
應該是很快啦，畢竟語言只是工具
邏輯思考才是要長期的訓練