2Sum

用哈希表(unordered_map)使得时间复杂度从O(n*n)降到O(n),空间复杂度从O(1)增到O(n);一边找一边插入哈希表

注意

在C++11以前要使用unordered_map需要

#include<tr1/unordered_map>//在unordered_map之前加上tr1库名,

using namespace std::tr1;//与此同时需要加上命名空间


#include<vector>
#include<tr1/unordered_map>


using namespace std;
using namespace std::tr1;

class twoSum {
public:
vector<int> f(vector<int>& nums, int target) {
unordered_map<int, int> hash;
vector<int> result;
for (int i = ; i < nums.size(); i++) {
int numToFind = target - nums[i];
if (hash.find(numToFind) != hash.end()) {
result.push_back(hash[numToFind]);
result.push_back(i);
return result;
}
hash[nums[i]] = i;
}
return result;
}
};
上一篇:abap 增强查找小程序


下一篇:[原创]-CMD命令设置IP地址