首页 > 编程语言 > 详细

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

时间:2020-04-02 12:56:08      阅读:189      评论:0      收藏:0      [点我收藏+]

本道题目我起初的想法是暴力寻找两个数之和,每次与目标数进行比对,这样的时间复杂度是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;
}

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

原文:https://www.cnblogs.com/gxyssd/p/12618738.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!