题目：https://leetcode-cn.com/problems/two-sum/
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

我的方法一：先排序后用双指针，O(nlogn)，O(n)

开始并没有想到官方使用哈希表来O（1）查找，而是想先对nums进行排序，但是排序后一些元素的index和之前的index会不同，所以排序后的nums需要记录之前的index；
然后通过双指针，从排序后的nums左右开始找，将双指针对应的元素相加
如果等于target，那么返回对应排序前的index，注意还得将小的index在前，大的index在后；
如果大于target，那么左移右指针；
如果小于target，那么右移左指针；

这个方法并不好，所以没有实现。

我的方法二：O(n)，O(n)

步骤

1. 先将nums存到一个哈希表里，key是元素的值，value是对应的位置index；
2. 从头开始遍历nums，先得到target-nums[index]的差，判断该差是否在哈希表里
3. 如果不在，继续第2步；如果在那么说明找到了对应的对，结果的第一个元素就是遍历的index，第二个元素就是对应的哈希表的value；

复杂度

时间：O(N)，遍历nums存到哈希表O(N)，遍历nums从哈希表找对应的差值O(N)，哈希表查找O(1)，所以总体是O(N)
空间：O(N)，使用了哈希表，存储了所有的nums元素

代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ret;
        unordered_map<int, int> m; // key is nums item, value is nums index

        int size = nums.size();

        //时间O(N), 空间O(N)
        for(int i = 0; i< size; i++){
            m[nums[i]] = i;
        }

        int index = 0;
        int another = 0;
        unordered_map<int, int>::iterator iter;

        //时间O(N)
        while(index < size){
            another = target - nums[index];

            //时间O(1)
            iter = m.find(another);
            if(iter != m.end() && index != iter->second){
                ret.push_back(index);
                ret.push_back(iter->second);
                return ret;
            }
            index++;
        }

        return ret;
    }
};