PythonでK-sumペアの最大数を見つけるプログラム

numsという配列と別の値kがあるとします。 1つの操作で、合計がkに等しいnumsから2つの要素を選択し、それらを配列から削除できます。アレイで実行できる操作の最大数を見つける必要があります。

したがって、入力がnums =[8,3,6,1,5] k =9のような場合、合計が9である[3,6]を削除してから、[8,1]を削除できるため、出力は2になります。 ]その合計も9です。

これを解決するには、次の手順に従います-

• counter：=numで表示される各アイテムの頻度を保持するマップ
• res：=0
• カウンターのnumごとに、
  を実行します。
  • 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）の商
• return 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))

入力

[8,3,6,1,5], 9

出力

2