C++刷题笔记：哈希表 map

两数之和

利用map容器“一对一”记录两数关系. 主要思路是查找对偶数other是否被记录， 如果无，则将当前元素作为对偶数存入map；如果存在对偶数，则返回二者的索引. 时间复杂度 $O\left(n\right)$O(n)， 空间复杂度 $O\left(n\right)$O(n)

class Solution 
{
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
        map<int, int> record;
        for(int i=0; i<nums.size(); i++)
        {
            int other = target - nums[i];
            if(record.count(other))
            {
                return {i, record[other]};
            }
            else
            {
                other = nums[i];
                record[other] = i;
            }
        }
        return {-1,-1};
    }
};