题目描述

在一个数组中，找到两个数的和为target，最后返回这两个数的下标。

样例

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

算法1

(暴力枚举) $O(n^2)$

C++ 代码

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

        vector<int> res;
        for(int i=0;i<nums.size();i++)
        {
            for(int j=i+1;j<nums.size();j++)
            {
                if(nums[i]+nums[j]==target)
                {
                    res = vector<int> ({i , j});//看不懂这一步
                }
            }
        }
        return res;
    }
};

一开始看不懂Line37，其实呢就是相当于又构建了一个（数组）vector，然后像里面添加了两个元素，等价于res.push_back(i);res.push_back(j);

算法2

(哈希) $O(n)$

unordered_map是C++中的哈希表，可以在任意类型与类型之间做映射。
1、定义 unordered_map<int,int>hash，既然可以任意类型转换，所以string,double都是可以替代 int 的
2、判断元素key 是否在hash表中 hash.count(key) == 0表示存在

参考文献

这么美丽的代码当然不是我想出来的：https://www.acwing.com/solution/content/47/

C++ 代码

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

        unordered_map <int,int> hash;
        vector<int> res;
        for(int i=0;i<nums.size();i++)
        {
            int another = target - nums[i];
            if (hash.count(another))
            {
                res.push_back(hash[another]);
                res.push_back(i);
                //res = vector<int> ({hash[another],i});
                break;
            }
            hash[nums[i]] = i;//记录每一个数字出现的下标
        }
        return res;
    }
};