参考文献
算法1
(暴力枚举) $O(n^2)$
两层循环遍历数组,判断 nums[i]+nums[j]是否等于target 。
C++ 代码
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
//暴力解法:枚举全部的可能性
vector<int> result;
for(int i=0; i<nums.size()-1; i++){
for(int j=i+1; j<nums.size(); j++){
if(nums[i]+nums[j]==target){
result.push_back(i);
result.push_back(j);
return result;
}
}
}
return result;
}
};
知识点
- 不要在for里面求数组长度,提前求好,防止出现数组长度变化的情况。
- 也可以返回一个pair作为简化,不用再建立一个vector
- vector的初始化方法:
res = vector<int>({j, i});
算法2
(哈希表) $O(n)$
遍历一遍数组:
1. 判断traget - nums[i]是否在哈希表中
2. 将元素插入哈希表中
C++ 代码
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
//哈希表
unordered_map<int, int> heap;
vector<int> res;
int len = nums.size();
for(int i = 0; i < len; i++){
auto item = heap.find(target - nums[i]);
if(item == heap.end()){ // 没找到
heap.insert({nums[i], i});
//nums.pop_back();
}else{ // 找到
res.push_back(i);
res.push_back(item->second);
//(*heap.find(nums.back())).second
//res.push_back(heap.find(nums.back())->second);
return res;
}
}
return res;
}
};
知识点
- 使用C++中的哈希表(插入和查询都是O(1))—— undered_map[HTML_REMOVED] heap
(1)用heap.count也可以查找一个元素是否在哈希表中
(2)哈希表插入:heap.insert 或者直接heap[“ABC”] = 5
(3) map 红黑树(一种平衡树)O(logn)
unordered_map 哈希表 O(1) - 遍历vector的时候不需要删除,大概是太久没写题,人傻了。。。
- 指针的访问可以直接用->,不需要再解引用.
//(*heap.find(nums.back())).second
//res.push_back(heap.find(nums.back())->second);
算法3
排序($O(nlogn)$)之后双指针
数组的很多题都可以排序之后解决,算套路了
最终版本
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
//哈希表
unordered_map<int, int> heap;
int len = nums.size(), another;
for(int i = 0; i < len; i++){
another = target - nums[i];
if(heap.count(another)) return {i, heap[another]};
else heap[nums[i]] = i;
}
return {};
}
};