K和数对的最大数目-LeetCode

1679. K 和数对的最大数目

🎯 问题描述（来源于LeetCode）

描述：
给你一个整数数组 nums 和一个整数 k。
在一步操作中，你可以选择数组中的两个数字，如果它们的和等于 k，就将它们从数组中移除。
请你返回你可以执行的最大操作数目。

说明：

• 这是一个哈希表计数结合贪心算法的问题。

• 核心逻辑是：对于每个数字 num，查找其互补数 k - num 是否存在。

• 如果存在，则配对成功，操作数加一，并减少互补数的计数。

• 如果不存在，则将当前数字加入哈希表，等待后续的互补数。

• 示例：

• 示例 1：

输入：nums = [1,2,3,4], k = 5
输出：2
解释：
- 移除 1 和 4 (1+4=5)
- 移除 2 和 3 (2+3=5)
- 总共 2 次操作。

• 示例 2：

输入：nums = [3,1,3,4,3], k = 6
输出：1
解释：
- 只能移除一对 3 (3+3=6)
- 剩下的数字无法组成和为 6 的数对。
- 总共 1 次操作。

💻 解题思路

思路1：哈希表 + 贪心匹配

思路1：代码实现

class Solution:
    def maxOperations(self, nums: List[int], k: int) -> int:
        # 哈希表：键为数字，值为该数字出现的次数
        count = defaultdict(int)
        ans = 0
        
        for num in nums:
            # 计算互补数
            complement = k - num
            
            # 检查互补数是否在哈希表中且数量大于0
            if complement in count and count[complement] > 0:
                # 如果存在，说明可以配对
                ans += 1
                # 减少互补数的计数（相当于从数组中移除）
                count[complement] -= 1
            else:
                # 如果不存在，将当前数字加入哈希表（等待后续的互补数）
                count[num] += 1
                
        return ans

思路1：📊 性能分析

• 时间复杂度：$O(N)$
  • 其中 $N$ 是数组 nums 的长度。
  • 我们只遍历数组一次，每次哈希表操作（查找、插入、更新）的平均时间复杂度都是 $O(1)$。
  • 总时间复杂度为 $O(N)$。
• 空间复杂度：$O(N)$
  • 哈希表 count 在最坏情况下需要存储 $N$ 个键值对。

思考

1. 贪心策略：

   • 我们想要最大化操作数目，因此每当遇到一个数字 num，如果它的互补数 k - num 已经出现过（且未被完全配对），我们就立即进行配对。
   • 这种“立即配对”的策略是贪心的，因为它不会错过任何可能的配对机会。

2. 哈希表的作用：

   • 哈希表用于记录尚未配对的数字及其出现次数。
   • 键是数字本身，值是该数字的剩余数量。

3. 逻辑流程：

   • 遍历每个数字 num。
   • 计算其互补数 complement = k - num。
   • 检查 complement 是否在哈希表中且数量大于 0：
     • 是：说明可以配对。操作数 ans 加 1，complement 的计数减 1（表示一个 complement 已被使用）。
     • 否：说明当前无法配对。将 num 的计数加 1（表示这个 num 等待后续的互补数）。

4. 处理重复数字：

   • 代码通过 count[complement] > 0 和 count[complement] -= 1 正确处理了重复数字的情况。
   • 例如，nums = [3,3,3], k = 6：
     • 第一个 3：complement = 3，不在哈希表中，count[3] = 1。
     • 第二个 3：complement = 3，在哈希表中且 count[3] = 1 > 0，配对成功，ans = 1，count[3] = 0。
     • 第三个 3：complement = 3，在哈希表中但 count[3] = 0，不配对，count[3] = 1。
   • 最终结果为 1，正确。

5. 边界情况：

   • 数组长度为 1：无法配对，返回 0。
   • 所有数字都相同且 2 * num != k：无法配对，返回 0。
   • 所有数字都相同且 2 * num == k：可以配对 N // 2 次。