题目描述
给你一个整数数组 nums 和一个整数 k 。
每一步操作中，你需要从数组中选出和为 k 的两个整数，并将它们移出数组。
返回你可以对数组执行的最大操作数。
示例 1：
1
2
3
4
5
6
| 输入：nums = [1,2,3,4], k = 5
输出：2
解释：开始时 nums = [1,2,3,4]：
- 移出 1 和 4 ，之后 nums = [2,3]
- 移出 2 和 3 ，之后 nums = []
不再有和为 5 的数对，因此最多执行 2 次操作。
|
示例 2：
1
2
3
4
5
| 输入：nums = [3,1,3,4,3], k = 6
输出：1
解释：开始时 nums = [3,1,3,4,3]：
- 移出前两个 3 ，之后nums = [1,4,3]
不再有和为 6 的数对，因此最多执行 1 次操作。
|
提示：
- 1 <= nums.length <= $10^{5}$
- 1 <= nums[i] <= $10^{9}$
- 1 <= k <= $10^{9}$
题解
使用哈希表解法：
从左到右遍历数组，同时用一个哈希表统计元素及其出现次数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int maxOperations(vector<int>& nums, int k) {
int res = 0;
unordered_map<int, int> u;
for (int x : nums) {
auto it = u.find(k - x);
if (it != u.end() && it->second) {
it->second--;
res++;
} else {
u[x]++;
}
}
return res;
}
}
|
