题目链接：https://leetcode.cn/problems/two-sum/
思路如下：
从前往后遍历
n
u
m
s
[
]
nums[\ ]
nums[ ] 数组，对于每个元素
n
u
m
s
[
i
]
nums[i]
nums[i] 我们做两件事：
- 判断
t
a
r
g
e
t
−
n
u
m
s
[
i
]
target - nums[i]
target−nums[i] 是否在哈希表中；
- 将
n
u
m
s
[
i
]
nums[i]
nums[i] 插入哈希表中；
由于数据保证有且仅有一组解，假设是
{
j
,
i
}
(
j
<
i
)
\left\{ j, i \right\}\ (j<i)
{j,i} (j<i)，则我们循环到
n
u
m
s
[
i
]
nums[i]
nums[i] 时，
n
u
m
s
[
j
]
nums[j]
nums[j] 一定在哈希表中，且有
n
u
m
s
[
j
]
+
n
u
m
s
[
i
]
=
=
t
a
r
g
e
t
nums[j] + nums[i] == target
nums[j]+nums[i]==target，所以我们一定可以找到解。
由于只扫描一遍，且哈希表 unordered_map 的插入和查询操作的复杂度是
O
(
1
)
O(1)
O(1)，所以总时间复杂度是
O
(
n
)
O(n)
O(n)。
C++代码如下：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
unordered_map<int, int> hash;
for (int i = 0; i < n; i++) {
int x = target - nums[i];
if (hash.count(x)) return {hash[x], i};
hash[nums[i]] = i;
}
return {};
}
};
