题目描述
给定一个整数数组 nums 和一个目标值 target，要求在数组中找出和为目标值的两个整数，并返回它们的数组下标。假设每种输入只会对应一个答案，且数组中同一个元素不能使用两遍。
输入格式
输入共 3 行：
- 第一行包含一个整数 n，表示数组的长度。
- 第二行包含 n 个整数，表示数组 nums 的元素。
- 第三行包含一个整数 target，表示目标值。
输出格式
输出共 1 行，包含两个整数，表示和为目标值的两个元素的数组下标，中间用空格分隔。
数据范围
2 ≤ n ≤ 10^4
-10^9 ≤ nums[i] ≤ 10^9
-10^9 ≤ target ≤ 10^9
输入样例1：
输出样例1：
输入样例2：
输出样例2：
注意事项
- 可以假设每种输入只会对应一个答案，但不能重复利用数组中的同一个元素。
- 暴力枚举法的时间复杂度为O(n²)，对于大规模数据可能会超时。
- 使用哈希表可以将时间复杂度降低到O(n)，空间复杂度为O(n)。
代码实现
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| #include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
vector<int> twoSumBruteForce(vector<int>& nums, int target)
{
int n = nums.size();
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
if (nums[i] + nums[j] == target)
{
return {i, j};
}
}
}
return {};
}
vector<int> twoSumHashTable(vector<int>& nums, int target)
{
unordered_map<int, int> numMap;
int n = nums.size();
for (int i = 0; i < n; i++)
{
int complement = target - nums[i];
if (numMap.find(complement) != numMap.end())
{
return {numMap[complement], i};
}
numMap[nums[i]] = i;
}
return {};
}
int main()
{
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++)
{
cin >> nums[i];
}
int target;
cin >> target;
vector<int> result = twoSumHashTable(nums, target);
if (!result.empty())
{
cout << result[0] << " " << result[1] << endl;
}
return 0;
}
|
时间复杂度
- 暴力枚举法时间复杂度：O(n²)，其中 n 是数组的长度。
- 哈希表法时间复杂度：O(n)，其中 n 是数组的长度。
- 空间复杂度：O(1)（暴力枚举法）或 O(n)（哈希表法，用于存储哈希表）。
代码解释
- 两数之和问题是一个经典的算法问题，可以用暴力枚举法或哈希表法来解决。
- 暴力枚举法的思想很简单：使用两层循环，遍历数组中所有可能的两个元素组合，检查它们的和是否等于目标值。这种方法的时间复杂度较高，但实现简单。
- 哈希表法的思想是：使用一个哈希表来存储已经遍历过的元素及其下标。在遍历数组的过程中，对于当前元素，我们计算它与目标值的差值，然后检查这个差值是否已经在哈希表中。如果在，则找到了符合条件的两个数；否则，将当前元素及其下标加入哈希表。这种方法的时间复杂度较低，但需要额外的空间来存储哈希表。
- 在实际应用中，哈希表法通常是更好的选择，因为它的时间复杂度更低。