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