题目链接:1. 两数之和
方法:哈希
解题思路
通过哈希记录每个\(nums[i]\)的下标\(i\),然后遍历\(nums\),找\(target - nums[i]\)的下标。
代码
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> idx;
for (int i = 0; i < nums.size(); i ++ ) idx[nums[i]] = i; // 最终idx[nums[i]]保存的是最后一个nums[i]的下标
for (int i = 0; i < nums.size(); i ++ ) {
if (idx.count(target - nums[i]) && idx[target - nums[i]] != i) {
return {i, idx[target - nums[i]]};
}
}
return {};
}
};
复杂度分析
时间复杂度:\(O(n)\);
空间复杂度:\(O(n)\)。