給一個整數(shù)數(shù)組，找到兩個數(shù)使得他們的和等于一個給定的數(shù) target。
你需要實現(xiàn)的函數(shù)twoSum需要返回這兩個數(shù)的下標, 并且第一個下標小于第二個下標。注意這里下標的范圍是 1 到 n，不是以 0 開頭。
注意事項
你可以假設只有一組答案。
您在真實的面試中是否遇到過這個題？
Yes
樣例
給出 numbers = [2, 7, 11, 15], target = 9, 返回 [1, 2].

/*
class Solution {
public:
    /*
     * @param numbers : An array of Integer
     * @param target : target = numbers[index1] + numbers[index2]
     * @return : [index1+1, index2+1] (index1 < index2)
     * 時間 復雜度 O(N^2)
     */
     /*
    vector<int> twoSum(vector<int> &nums, int target) {
        // write your code here
        vector<int> res;
        for(int i=0;i<nums.size();i++){
            for(int j=i+1;j<nums.size();j++){
                if(nums[i]+nums[j]==target){
                    res.push_back(i+1);
                    res.push_back(j+1);
                    return res;
                }
            }
        }

        return res;
    }
};
*/

class Solution {
public:
    /*
    * @param numbers : An array of Integer
    * @param target : target = numbers[index1] + numbers[index2]
    * @return : [index1+1, index2+1] (index1 < index2)
    * 時間復雜度 O(N)
    * 空間復雜度 O(N)
    */
    vector<int> twoSum(vector<int> &nums, int target) {
        // write your code here
        set<int> res;
        
        //構(gòu)建一個map，實現(xiàn)O(1)的元素查找
        map<int, int > m;
        for (int i = 0; i < nums.size(); i++) {
            int key = nums[i];
            int val = i;
            m[key] = val;
        }

        for (int i = 0; i < nums.size(); i++) {
            int left = target - nums[i];
            auto it=m.find(left);

            if (it != m.end()) {
                int index = i + 1;
                int left_index = m[left] + 1;
                // 排除自身等于自身的情況，比如 這樣 [1,0,-1], 0 
                if (index != left_index) {
                    res.insert(index);
                    res.insert(left_index);
                }
            }
        }

        vector<int> ret(res.begin(), res.end());
        return ret;
    }
};