leetcode-1 two sum

題意:
在一個陣列裡面,求出相加為目標值得兩數,其分別的座標為何,題目保證只有一組解


解題思路
這題解題思路很簡單,就是要了解c++ STL map的使用,來把演算法的複雜度降到$O(nlog n)$,
p.s: 亦可使用hashmap,也就是C++中的unordered_map來實現,其複雜度最佳可到$O(n)$,但hash你知道的嗎XD,可能會讓複雜度變超大!


code如下:

class Solution {
public:
    map<int,int>p;
    vector<int> twoSum(vector<int>& nums, int target) {
        int len=nums.size();
        for(int i=0;i<len;i++)
        {
            if(p.find(nums[i])!=p.end())
            {
                vector<int>ans;
                ans.push_back(p.find(nums[i])->second);
                ans.push_back(i);
                return ans;
            }
            p.insert(make_pair(target-nums[i],i));
        }
    }
};