一、题目描述
二、解题思路
这道题当然可以暴力，这样时间复杂度为 O ( n 2 ) O(n^2) O(n2)。所以我采用哈希表来解决。
遍历一次数组，将其与下标的 p a i r ( v a l , i n d e x ) pair(val, index) pair(val,index)插入到哈希表中。所以我们根据当前的数字去找 t a r g e t − n u m s [ i ] target - nums[i] target−nums[i]是否在哈希表里即可。但是如果出现 t a r g e t − n u m s [ i ] = = n u m s [ i ] target - nums[i] == nums[i] target−nums[i]==nums[i]的情况时，哈希表会根据 k e y key key查找到与当前的 n u m s [ i ] nums[i] nums[i]相同的下标 i n d e x index index，导致出错，所以只有在 t a r g e t − n u m s [ i ] target - nums[i] target−nums[i]作为 k e y key key时映射出来的元素的下标与当前元素不等时，才证明找到。
三、解题代码
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> ump; //val, index
vector<int> sln;
for(int i = 0; i < nums.size(); i++){
if(ump.find(nums.at(i)) == ump.end())
ump.insert(make_pair(nums.at(i), i));
if(ump.find(target - nums.at(i)) != ump.end()){
if(ump.find(target - nums.at(i))->second != i){
sln.push_back(ump.find(target - nums.at(i))->second);
sln.push_back(i);
return sln;
}
}
}
return sln;
}
};
京公网安备 11010502036488号