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

0
10

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

<

发布回复

请输入评论!
请输入你的名字