1. 两数之和
2 min
题目
思路
遍历数组，用哈希表存储数值及其索引，查找 target - nums[i] 是否存在且非同一元素
复杂度
- 时间复杂度: O(n)
- 空间复杂度: O(n)
代码
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int>ans;
map<int,int>mp;
for(int i = 0;i < nums.size();i++){
mp[nums[i]] = i;
}
for(int i = 0; i < nums.size();i++){
if(mp[target - nums[i]] and mp[target - nums[i]]!=i){
ans.push_back(i);
ans.push_back(mp[target - nums[i]]);
break;
}
}
return ans;
}
};