题目

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

思路

第一种：暴力，双重循环，时间复杂度O(n^2)
第二种：排序后，左右两侧搜索，时间复杂度O(n*log(n))

实现一

太久不写c++，首先尝试第一种熟悉一下。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for(int i=0; i<nums.size(); i++){
            for(int j=0; j<nums.size(); j++){
                if(i==j)
                    continue;
                if(nums[i]+nums[j]==target)
                    return vector<int>{i,j};
            }
        }
    }
};

本以为会超时，但是没想到过了=_=
不过运行时间的排名实在难看，在后4.39%

实现二

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<pair<int,int>> tmp;
        for(int i=0; i<nums.size(); i++){
            tmp.push_back(make_pair(nums[i], i));
        }
        sort(tmp.begin(), tmp.end());
        int i=0;
        int j=tmp.size()-1;
        while(tmp[i].first + tmp[j].first != target){
            if(tmp[i].first + tmp[j].first > target)
                j--;
            else
                i++;
            if(i>=j){
                break;
            }
        }
        return vector<int> {tmp[i].second, tmp[j].second};
    }
};

第一个考虑的问题是如何保存排序后的索引值，去了解了map，但是其键值不能重复。现在想想好像可以用multimap，当时没想到，就用了vector<pair<int,int>>再加上sort()实现。
第二个问题出在左右搜索上，一开始想着要从中间target/2处开始搜索，所以想了半天如何将lower_bound()用到排序好的数据上来。为此花了很多时间，甚至还尝试了自己写个lower_bound函数，但是总是报超时，也不知道为什么。后来一想从中间开始向两边搜索还要考虑一些边界问题，为什么不能从两边往中间搜索呢。一试就成功了，这次击败了82.02%的选手。
代码比较简单，这里就不阐述具体思路了，主要是熟悉下STL的运用。

思考

看了别人的代码，发现还有一种思路就是使用unordered_map加快查询，使查询时间复杂度为O(log(n))，这样通过对每个值查找配对的值也可以达到总体O(nlog(n))的时间复杂度。但是不知道为什么他不会因为重复的元素而报错，难道是unordered_map支持吗，这个还有待考证。