题目描述：
思路
时间复杂度为 $O(n^2)$ 的算法思路很简单，直接采用暴力法使用两层循环遍历每一种可能，判断是否存在答案。
这里详细说明一下时间复杂度为 $O(n)$ 的算法，暴力法之所以慢是因为寻找 target - x 的时间复杂度过高。那有没有什么方法可以加速寻找元素 target - x 是否存在且存在时可以知道其索引呢？有的，那就是使用哈希表来做，以target - x 为key，以索引为value。这样，寻找target - x的时间复杂度就变为了 $O(1)$，极大地提高了效率。
具体来说，对于遍历的每个元素，先判断其target - x是否存在，若存在，则直接返回对应的下标；若不存在，则将x存入哈希表，方便后续的查找。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
// 暴力法
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 {};
}
};
// 哈希表法
class Solution
{
public:
vector<int> twoSum(vector<int>& nums, int target)
{
unordered_map<int, int> hashtable;
for (int i = 0; i < nums.size(); ++i)
{
unordered_map<int, int>::iterator it = hashtable.find(target - nums[i]);
if (it != hashtable.end())
{
return { it->second, i };
}
hashtable[nums[i]] = i;
}
return {};
}
};
|
zyz