1679. K 和数对的最大数目
1679. K 和数对的最大数目
🟠 🔖 数组
哈希表
双指针
排序
🔗 力扣
LeetCode
题目
You are given an integer array nums
and an integer k
.
In one operation, you can pick two numbers from the array whose sum equals k
and remove them from the array.
Return the maximum number of operations you can perform on the array.
Example 1:
Input: nums = [1,2,3,4], k = 5
Output: 2
Explanation: Starting with nums = [1,2,3,4]:
- Remove numbers 1 and 4, then nums = [2,3]
- Remove numbers 2 and 3, then nums = []
There are no more pairs that sum up to 5, hence a total of 2 operations.
Example 2:
Input: nums = [3,1,3,4,3], k = 6
Output: 1
Explanation: Starting with nums = [3,1,3,4,3]:
- Remove the first two 3's, then nums = [1,4,3]
There are no more pairs that sum up to 6, hence a total of 1 operation.
Constraints:
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= k <= 10^9
题目大意
给你一个整数数组 nums
和一个整数 k
。
每一步操作中,你需要从数组中选出和为 k
的两个整数,并将它们移出数组。
返回你可以对数组执行的最大操作数。
示例 1:
输入: nums = [1,2,3,4], k = 5
输出: 2
解释: 开始时 nums = [1,2,3,4]:
- 移出 1 和 4 ,之后 nums = [2,3]
- 移出 2 和 3 ,之后 nums = []
不再有和为 5 的数对,因此最多执行 2 次操作。
示例 2:
输入: 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
解题思路
使用哈希表(Map):
- 使用一个
Map
来存储每个数字的频率,以便快速查找所需配对数字的数量。
- 使用一个
遍历数组:
- 对于数组中的每个数字,计算其配对数字(
k - num
)。 - 检查哈希表中是否存在这个配对数字。
- 对于数组中的每个数字,计算其配对数字(
配对处理:
- 如果配对数字存在,则增加操作次数
res
。 - 更新配对数字的频率,如果频率减到零,则从
Map
中删除该数字。 - 如果配对数字不存在,则将当前数字的频率添加到
Map
中。
- 如果配对数字存在,则增加操作次数
返回结果:
- 返回可以进行的最大操作次数
res
。
- 返回可以进行的最大操作次数
复杂度分析
- 时间复杂度:
O(n)
,其中n
是数组的长度,只需遍历数组一次。 - 空间复杂度:
O(n)
,用于存储Map
中每个数字的频率。
代码
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var maxOperations = function (nums, k) {
let map = new Map(),
res = 0;
for (let num of nums) {
const another = k - num; // 计算配对数字
if (map.has(another)) {
// 找到一对,增加操作次数
res++;
// 更新配对数字的计数
const anotherCount = map.get(another) - 1;
if (anotherCount === 0) {
map.delete(another); // 如果计数为0,删除该数字
} else {
map.set(another, anotherCount); // 更新计数
}
} else {
map.set(num, (map.get(num) || 0) + 1); // 更新当前数字的计数
}
}
return res; // 返回最大操作次数
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
1 | 两数之和 | [✓] | 数组 哈希表 | 🟢 | 🀄️ 🔗 |
1711 | 大餐计数 | 数组 哈希表 | 🟠 | 🀄️ 🔗 | |
2491 | 划分技能点相等的团队 | [✓] | 数组 哈希表 双指针 1+ | 🟠 | 🀄️ 🔗 |