题意理解

找出数组中和等于目标值的两个数，输出它们的下标，注意先输出小的下标。输出结果存在且唯一。

方法一

题目要求两个数值对应的index，首先想到双指针的方法。

先对数组进行排序，注意在排序时，原先的index也要跟着数值一起交换位置，否则最后输出新的index是错误的。这就需要我们自己定义一个结构体，里面存放数值和对应的旧index。

两个指针（非数据结构的指针）i,j分别指向开头和结尾，如果number[i]+number[j]==target即得到答案。若和小于target，说明加数小了，i就右移；若和大于target，说明加数大了，j左移。每一个数只要扫一遍就可以了。
示意图如下：

证明算法不会错过解：
当i扫到number[i']的时候，不可能和j右侧的数值相加等于target。因为之前j位于j'（j'>j）的时候，指针i右移直到两数之和大于target时停止，此时i<i'，所以number[i']+number[j']一定大于target。

具体代码如下：

class Solution {
public:
    /**
     * 
     * @param numbers int整型vector 
     * @param target int整型 
     * @return int整型vector
     */
    //定义结构体Num_index，把数值和原先的index都对应地存储起来
    typedef struct {
        int number;
        int index;
    }Num_index;

    //需要自己写sort函数里面的比较方法，这里比较number的数值
    static bool compare(Num_index a, Num_index b) {
        return (a.number < b.number);
    }

    vector<int> twoSum(vector<int>& numbers, int target) {
        //定义一个Num_index类型的数组，将数值及其原先的index存入
        vector<Num_index> num_index;
        for (int i=0;i<numbers.size();i++) {
            Num_index x;
            x.number = numbers[i];
            x.index = i;
            num_index.push_back(x);
        }
        sort(num_index.begin(), num_index.end(), compare);
        vector<int> ans;

        //排序后，从两端向中间搜索；当i>=j时搜索完毕。
        int i=0,j=numbers.size()-1;
        while (i<j) {
            if (num_index[i].number+num_index[j].number == target) {
                //注意先输出原先index小的值
                ans.push_back(min(num_index[i].index,num_index[j].index)+1);
                ans.push_back(max(num_index[i].index,num_index[j].index)+1);
                return (ans);
                break;
            }
            else if (num_index[i].number+num_index[j].number < target) {
                i++;
            }
            else j--;
        }
        return ans;
    }
};

时间复杂度：快速。使用快速排序的时间为；双指针遍历时，每个数值只经过了一遍，为。
空间复杂度：。创建了一个结构体数组重新存储数值和对应的旧index。

方法二

当我们遍历到某个numbers[i]时，就要看target-numbers[i]是否在数组中。这本来是一个双重循环，需要O(n^2)的时间。

考虑使用哈希表来标记某个数是否存在于数组中，把双重循环改为并行的两次循环。先遍历一遍来建立哈希表mymap，哈希规则为mymap[numbers[i]] = i；再遍历一遍数组number，查看target-numbers[i]是否在哈希表中，注意两个加数不能重复。

哈希表示意图如下：

具体代码如下：

class Solution {
public:
    /**
     * 
     * @param numbers int整型vector 
     * @param target int整型 
     * @return int整型vector
     */
    vector<int> twoSum(vector<int>& numbers, int target) {
        unordered_map<int, int> mymap;
        //建立哈希表
        for (int i=0;i<numbers.size();i++) {
            mymap[numbers[i]] = i;
        }
        vector<int> ans;

        for (int i=0;i<numbers.size();i++) {
            int d = target - numbers[i];
            //先判断target与numbers[i]的差是否在hash中，其次还要判断是否重复了。
            if (mymap.count(d)!=0 && mymap.at(d)!=i) {
                ans = {i+1, mymap.at(d)+1};
                break;
            }
        }
        return ans;
    }
};

时间复杂度：。建立哈希表和使用哈希表进行查找的时间都为。
空间复杂度：。建立一个哈希表需要的空间。