当前位置： 移动技术网 > IT编程>开发语言>C/C++ > 在数组中寻找两个数之和等于目标数

在数组中寻找两个数之和等于目标数

2020年04月02日  | 移动技术网IT编程  | 我要评论

走迷宫双人版,qq餐厅刷钱器,林俊杰给别人写的歌

本道题目我起初的想法是暴力寻找两个数之和，每次与目标数进行比对，这样的时间复杂度是o（n2）。

改进：

我使用散列表将数组元素散列存储，这样便可以对元素进行o（1）访问，从而实现在o（n）的时间复杂度解决该问题。

#include  <iostream>
#include <cstdio>
#include <vector>
#include <map>


using namespace std;

vector<int> twosum(vector<int>& nums, int target) ;
int main()
{
    int vector_num, target ;
    cin>>vector_num;
    vector<int> nums(vector_num);
    for(int i = 0; i < vector_num; ++i)
    {
        cin >> nums.at(i);
    }
    cin>>target;
    vector<int> ans = twosum(nums,target);
    for(int i = 0;i<ans.size();++i)
    {
        cout<<ans.at(i)<<endl;
    }
    return 0;
}

vector<int> twosum(vector<int>& nums, int target)
{
    vector<int> ans;
    map<int, int> hashmap;
    for (int i = 0; i < nums.size(); i++)
    {
        hashmap.insert(pair<int, int>(nums[i], i));
    }
    for (int i = 0; i < nums.size(); i++)
    {
        int complement = target - nums[i];
        map<int, int>::iterator iter;
        iter = hashmap.find(complement);
        if (iter != hashmap.end() && hashmap.at(complement) != i)
        {
            ans =  {i, hashmap.at(complement) };
        }
    }
    return ans;
}

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网