给定一个整数数组 nums 和一个整数 target ,找到数组里的两个数的和等于 target,返回这两个数在数组中的下标,假设每个输入都只有一个解决方案,并且不能两次使用相同的元素。可以按任何顺序返回答案。
注意:数组无序。
输入: nums = [2,7,11,15], target = 9
输出: [0,1]
解释:因为 2 + 7 = 9,数字 2和7的在数组中的下标分别为 0和1,所以输出 [0,1]。
遍历数组 nums,使用哈希表(unordered_map类型)存储数组中遍历过的元素,每遍历一个元素 nums[i],查找哈希表中是否存在 target - nums[i],如果不存在,则将 nums[i] 和 下标 i 存储到哈希表中,如果存在,则返回当前下标以及哈希表中 target - nums[i] 对应的值。
通俗一点的说就是:每次在哈希表中查找 target - nums[i] 是否存在,一直查询到一个结果。
class Solution
{
public:
vector<int> twoSum(vector<int>& nums, int target)
{
unordered_map<int, int> hashTable; //哈希表
vector<int> ret;
for(int i = 0; i < (int)nums.size(); ++i) { //依次遍历每一个元素
if(hashTable.count(target - nums[i])) {//查找 target - nums[i] 是否存在
ret.push_back(i); // 存储下标
ret.push_back(hashTable[target - nums[i]]); //存储下标
return ret;
}
hashTable[nums[i]] = i;
}
return ret;
}
};
时间复杂度:使用哈希表存储,每次查询的时间是O(1),最多遍历 n 个元素,故时间复杂度为 O(n)。
本文系转载,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文系转载,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。