Repository navigation
Expand file tree
/
Copy path1-two-sum.cpp
More file actions
107 lines (99 loc) · 2.48 KB
/
Copy path1-two-sum.cpp
File metadata and controls
107 lines (99 loc) · 2.48 KB
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
//给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
//
// 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
//
// 你可以按任意顺序返回答案。
//
//
//
// 示例 1:
//
//
//输入:nums = [2,7,11,15], target = 9
//输出:[0,1]
//解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
//
//
// 示例 2:
//
//
//输入:nums = [3,2,4], target = 6
//输出:[1,2]
//
//
// 示例 3:
//
//
//输入:nums = [3,3], target = 6
//输出:[0,1]
//
//
//
//
// 提示:
//
//
// 2 <= nums.length <= 10⁴
// -10⁹ <= nums[i] <= 10⁹
// -10⁹ <= target <= 10⁹
// 只会存在一个有效答案
//
//
// 进阶:你可以想出一个时间复杂度小于 O(n²) 的算法吗?
// Related Topics 数组 哈希表 👍 14169 👎 0
#include "headers.h"
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
vector<int> twoSum2(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 {};
// hash 法
unordered_map<int, int> hash;
for (int i = 0; i < nums.size(); ++i) {
// 先判断目标值是否存在于hash表中
auto it = hash.find(target - nums[i]);
if (it != hash.end()) {
return {it->second, i};
}
hash[nums[i]] = i;
}
return {};
}
vector<int> twoSum(vector<int> &nums, int target) {
unordered_map<int, int> hash;
// 遍历一次即可
for (int i = 0; i < nums.size(); i++) {
// t 就是第二个数
int t = target - nums[i];
auto it = hash.find(t);
if (it != hash.end()) {
// 找到的情况下,当前i是第二个数的位置了
return {it->second, i};
} else { // 把第一个数填入到 hash 中
hash[nums[i]] = i;
}
}
return {};
}
};
//leetcode submit region end(Prohibit modification and deletion)
int main() {
Solution s;
vector<int> arr{2, 7, 11, 15};
auto res = s.twoSum(arr, 9);
showVector(res);// 0,1
arr = {3, 2, 4};
res = s.twoSum(arr, 6);
showVector(res);// 1,2
arr = {3, 3};
res = s.twoSum(arr, 6);
showVector(res);// 0,1
}