用 Python 编写程序来查找最大数量的 K-sum 对

pythonserver side programmingprogramming更新于 2025/12/2 1:48:17

假设我们有一个名为 nums 的数组和另一个值 k。在一次操作中，我们可以从 nums 中选择两个总和等于 k 的元素，然后将它们从数组中删除。我们必须找到可以对数组执行的最大操作数。

因此，如果输入为 nums = [8,3,6,1,5] k = 9，则输出将为 2，因为我们可以删除总和为 9 的 [3,6]，然后删除总和也是 9 的 [8,1]。

为了解决这个问题，我们将遵循以下步骤 −

counter := 一个映射，保存 nums 中存在的每个项目的频率
res := 0
对于 counter 中的每个数字，执行
- 如果 counter[k-num] 非零，则
  - 如果 num 与 k - num 不同，则
    - res := res + counter[num] 的最小值和counter[k-num]
    - counter[k-num] := 0
    - counter[num] := 0
  - 否则，
    - res := res + (counter[num] / 2) 的商
返回 res

示例

让我们看看下面的实现以便更好地理解 −


from collections import Counter
def solve(nums, k):
   counter = Counter(nums)
   res = 0
   for num in counter:
      if counter.get(k-num, 0):
         if num != k - num:
            res += min(counter[num], counter[k-num])
            counter[k-num] = 0
            counter[num] = 0
         else:
            res += int(counter[num] / 2)

   return res

nums = [8,3,6,1,5]
k = 9
print(solve(nums, k))