题目描述
在数组中找到两个数的和为target的下标。注意返回的2个下标的不能相等。
思路
用哈希表存储数组中的每个元素。
根据nums[i]+nums[j]=target
在遍历整个数组的时候——可以确定nums[i]
那么就可以确定nums[j]=target-nums[i]
为了避免出现返回2个下标相同的情况
边遍历元素边存储到哈希表中，这样当前的值没有进入哈希表就不会被查找到。
其他思路
双重循环O(N^2)
排序(注意用一个数组存储下标同时排序)+双指针O(N*logN)
代码
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> hash;
hash[nums[0]]=0;
for(int i=1;i<nums.size();i++)
{
if(hash.count(target-nums[i]))
return {i,hash[target-nums[i]]};
hash[nums[i]]=i;
}
return {};
}
};