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

更新于： 12-Oct-2021

283 次浏览

开启你的 职业生涯

完成课程获取认证

开始学习
广告