Python 中計算使元素之和為 2 的冪的索引對的程式

假設我們有一個名為 nums 的數字列表。我們必須找到索引對 i, j 的數量，其中 i < j，使得 nums[i] + nums[j] 等於某些 0 >= k 的 2^k。

因此，如果輸入類似於 nums = [1, 2, 6, 3, 5]，則輸出為 3，因為存在三個對和 (6, 2)：和為 8，(5, 3)：和為 8，(1, 3)，和為 4。

要解決此問題，我們將遵循以下步驟 -

• res := 0

• c := 包含中各個元素頻率的地圖

• 對於 nums 中的每個 x，請執行以下操作

  • 對於 j 的範圍為 0 至 31，請執行以下操作

    • res := res + c[(2^j) - x]

  • c[x] := c[x] + 1

• 返回 res

示例

讓我們檢視以下實現以獲得更好的理解

from collections import Counter
def solve(nums):
   res, c = 0, Counter()
   for x in nums:
      for j in range(32):
         res += c[(1 << j) - x]
      c[x] += 1
   return res

nums = [1, 2, 6, 3, 5]
print(solve(nums))

輸入

[1, 2, 6, 3, 5]

輸出

3

Arnab Chakraborty

更新於： 12-Oct-2021

283 次瀏覽

開啟你的 職業生涯

完成課程獲取認證

開始學習