rw note

找个最简单的题目…

暴力肯定会超时，map(或者hash)，之后查询 target - num 是否存在，时间复杂度O（lgN）。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {

        vector<int> index;
        map<int, int> mp;
        for (int i=0; i<nums.size(); i++) {
            mp[nums[i]] = i;
        }

        for (int i=0; i<nums.size();i++) {
            map<int,int>::iterator it;
            it = mp.find(target-nums[i]);
            if (it!=mp.end()) {
                ///3-->3
                if (i==it->second) {
                    continue;
                }
                index.insert(index.end(), i);
                index.insert(index.end(), it->second);
                break;
            }
        }

//        for (int i=0; i<nums.size(); i++) {
//            for (int j=i; j<nums.size(); j++) {
//                if (nums[i]+nums[j]==target) {
//                    index.insert(index.end(), i);
//                    index.insert(index.end(), j);
//                    return index;
//                }
//            }
//        }
        return index;
    }
};

int main(int argc, const char * argv[]) {
    // insert code here...
//    cout << "Hello, World!n";

    vector<int> nums;
    nums.insert(nums.end(), 3);
    nums.insert(nums.end(), 2);
    nums.insert(nums.end(), 4);
    int target = 6;


    Solution sol;
    vector<int> index = sol.twoSum(nums, target);
    for (int i=0; i<index.size(); i++) {
        cout << index[i]<<endl;
    }
    return 0;
}