LeetCode 1 - 两数之和

哈希

使用一个哈希表记录 mp 每个数字出现的位置，mp[x] 表示数字 x 在原数组中的下标为 mp[x]-1（因为C++哈希表默认值为 0，所以向右偏移 1 位）. 从左向右遍历数组，并更新 mp，如果遍历到下标 i ，发现此时 mp[target-nums[i]]>0 ，说明 target-nums[i] 之前就出现过，符合要求，返回结果即可.

时间、空间复杂度均为 $O(n)$O(n).

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> mp;
        vector<int> ans;
        int n=nums.size();
        for(int i=0;i<n;++i){
            if(mp[target-nums[i]]){
                ans.push_back(mp[target-nums[i]]-1);
                ans.push_back(i);
                return ans;
            }
            mp[nums[i]]=i+1;
        }
        return ans;
    }
};