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

解题思路

1. 使用哈希表（Map）：

   • 使用一个 Map 来存储每个数字的频率，以便快速查找所需配对数字的数量。

2. 遍历数组：

   • 对于数组中的每个数字，计算其配对数字（k - num）。
   • 检查哈希表中是否存在这个配对数字。

3. 配对处理：

   • 如果配对数字存在，则增加操作次数 res。
   • 更新配对数字的频率，如果频率减到零，则从 Map 中删除该数字。
   • 如果配对数字不存在，则将当前数字的频率添加到 Map 中。

4. 返回结果：

   • 返回可以进行的最大操作次数 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+