面试题 16.24. 数对和

🎯 问题描述（来源于LeetCode）

描述：
设计一个算法，找出数组中两数之和为指定值的所有整数对。一个数只能属于一个数对。
给定一个整数数组 nums 和一个目标值 target，请返回所有满足条件的数对。

说明：

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

  • 核心逻辑是：对于每个数字 num，查找其互补数 target - num 是否已经出现过且未被使用。

  • 如果存在，则组成一个数对，并减少互补数的可用数量。

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

  • 示例：

  • 示例 1：

1
2
3
4
5
输入：nums = [5,6,5], target = 11
输出：
解释：
- 5 + 6 = 11
- 第一个 5 和 6 配对，第二个 5 无法配对。
  • 示例 2：
1
2
3
4
输入：nums = [5,6,5,6], target = 11
输出：[[5,6],[5,6]]
解释：
- 可以组成两对 (5,6)。

💻 解题思路

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

思路1：代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:
        # 哈希表：键为数字，值为该数字出现的次数（未被配对的数量）
        count = defaultdict(int)
        ans = []
        
        for num in nums:
            # 计算互补数
            complement = target - num
            
            # 检查互补数是否在哈希表中且数量大于0
            if complement in count and count[complement] > 0:
                # 如果存在，说明可以配对
                ans.append([complement, num])
                # 减少互补数的计数（相当于从可用池中移除）
                count[complement] -= 1
            else:
                # 如果不存在，将当前数字加入哈希表（等待后续的互补数）
                count[num] += 1
                
        return ans

思路1：📊 性能分析

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

思考

  1. 贪心策略：

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

  2. 哈希表的作用：

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

  3. 逻辑流程：

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

  4. 处理重复数字：

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

  5. 边界情况：

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