1. 两数之和

Problem: 1. 两数之和

思路

-用map存储nums的<值,下标>

• 遍历nums,
  • 如果map中的target - nums[i]存在且不是nums[i]本身则说明有,两数之和的数return,
  • 没有继续遍历,将target加入map中

复杂度

• 时间复杂度:

$O(n)$

• 空间复杂度:

$O(n)$

Code

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> map;
        for(int i = 0; i < nums.size(); i++) {
            auto tar = map.find(target - nums[i]);
            if(tar != map.end()) {
                return {tar->second,i};
            } else {
                map.insert(pair<int,int>(nums[i],i));
            }
        }      
        return {};
    }
};