两数之和
1、暴力求解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
for(int i=0;i<nums.size();i++)
{
for(int j=i+1;j<nums.size();j++)
{
if(nums[i]+nums[j]==target)
return {i,j};
}
}
return {};
}
};
|
时间复杂度为$O(n^2)$，空间复杂度$O(1)$
2、哈希表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> Hash;
for (int i = 0; i < nums.size(); ++i) {
unordered_map<int,int>::iterator iter = Hash.find(target - nums[i]);
if (iter!= hash.end()) {
return {iter->second, i};
}
hash[nums[i]] = i;
}
return {};
}
};
|
时间复杂度为$O(1)$，空间复杂度$O(n)$。
C++中的哈希表
需要头文件：
1
| #include <unordered_map>
|
定义方式，两个类型分别是键、值的数据类型：
1
| unordered_map<int,int> Hash;
|
添加值：
1
2
3
| Hash.insert({1,2});
Hash.insert({make_pair(1,2)});
Hash[1]=2;
|
迭代器：
1
| unordered_map<int,int>::iterator iter;
|
清除：
1
2
| Hash.erase(1);
Hash.clear();
|
查找，若找不到，返回的是Hash.end()：
利用迭代器访问变量：
1
2
| iter->first;
iter->second;
|