【牛客-算法】NC61 两数之和（哈希表的运用，C++）

前言

🔥 该专栏作为算法题笔记，记录算法的思路、遇到的问题，以及能跑的代码，持续更新中！

🔥 推荐一款面试、刷题神器牛客网：👉开始刷题学习👈

题目描述

• 原题链接：NC61 两数之和
  
• 描述
  
• 给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。
  （注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）
  
• 数据范围
  

2≤len(numbers)≤105,−10≤numbersi≤109,0≤target≤109

要求

空间复杂度O ( n ) ，时间复杂度O ( n l o g n )  

算法设计思路

直接两层循环暴力搜索会超时。因此，我们可以使用哈希表（散列表）来节省时间，只需遍历一次数组。数组的下标是连续的数字，而哈希表的下标可以是不连续的数字、字符串。

用哈希表的左值（哈希表的下标）存放数组中的数，右值存放对应的数组下标。读到数组中的数字numbers[i]时，计算target与它的差值d，如果哈希表中存在下标d，则返回结果。否则将当前数字放入哈希表。

图中我们遍历到数组中的数字4时，发现 h[6-4]=h[2]=0，就知道与4和为6的数字在数组中的下标是0。

算法实现（C++）

#include<map>
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> r;          //返回找到的下标
        map<int, int> h;        //哈希表
        map<int, bool> pass;    //h中左值存在则为true
        for(int i = 0; i < numbers.size(); i++){
            int d = target - numbers[i];
            if(pass[d] != 0){
                r.push_back(h[d]+1);
                r.push_back(i+1);
            }
            else{
                h[numbers[i]] = i;
                pass[numbers[i]] = 1;
            }
        }
        return r;
    }
};

运行结果