题解 | #两数之和#

可能是自己理解有问题，一开始认为返回的解可能有多个，但是题目给的接口又是只返回一个，就去直接看答案了。

显而易见的一个思路是，暴力，然而，这道题，暴力法超时了，代码如下↓

vector<int> twoSum(vector<int>& numbers, int target) {
    // write code here
    vector<int> ans;
    // 数组为空
    if(!numbers.size()) {
        return ans;
    }
    for(int i = 0; i < numbers.size() -1 ; i++) {
        for(int j = i + 1; j < numbers.size(); j++) {
            if(numbers[i] + numbers[j] == target) {
                ans.push_back(i + 1);
                ans.push_back(j + 1);
                return ans;
            }
        }
    }
    return ans;
}

另一个思路是hash表，直接使用map来简历映射，注意，mp.find函数有点意思，当无法在mp中找到值的时候，会直接返回mp.end()，因此著需要判断find的返回值是啥，就知道哈希表中是否存在想要的值，其他的就喊简单了

class Solution {
public:
    /**
     * 
     * @param numbers int整型vector 
     * @param target int整型 
     * @return int整型vector
     */
vector<int> twoSum(vector<int>& numbers, int target) {
    int size = numbers.size();
    vector<int> ans;
    unordered_map<int,int> mp;
    for(int i = 0; i < size; i++) {
        // find函数若返回end则说明没找到，反之则找到了
        // 下面这个if说明，返回的值不等于end，也就是找到了
        if(mp.find(target - numbers[i]) != mp.end()) {
            ans.push_back(mp[target - numbers[i]] + 1); //这个必然在前面
            ans.push_back(i + 1);//这个必然在后面
            break;
        }
        else {
            mp[numbers[i]] = i;
        }
    }
    return ans;
}
};