计算和为2的幂的偶对数量|进阶篇

来源：GeeksforGeeks

给定一个包含N个正整数的数组arr[]，目标是找出数组中的所有偶对(arr[i], arr[j])，使这些偶对的和为2的某个幂次。

实例：

输入：arr[] = {1, -1, 2, 3}

输出：5

解析：(1, 1), (2, 2), (1, 3), (-1, 3), (-1, 2)是符合条件的偶对，因为它们的和为2的幂。

输入：arr[] = {1, 1, 1}

输出：6

基础解法：最直接的方法是枚举数组中的所有可能偶对，并逐一检查每个偶对的和是否为2的幂。这种方法虽然直观，但效率较低。

时间复杂度：O(N^2)。

空间复杂度：O(1)。

优化解法：利用哈希表可以显著提高算法的效率。具体步骤如下：

• 构建一个哈希表来记录数组arr[]中每个元素出现的频率。
• 初始化一个计数器count，用于记录满足条件的偶对数量。
• 遍历从0到31的范围，生成2的所有幂次，即从2^0到2^31。
• 遍历数组，对于每个生成的2的幂次key，检查哈希表中是否存在key - arr[j]。
• 如果存在，则将count增加map[key - arr[j]]的值，表示找到了一对和为2的幂次的偶对(arr[j], key - arr[j])。
• 最终输出count / 2作为结果，因为每对在计算过程中会被重复计算一次。

以下是优化解法的C++和Java实现：

C++ 实现

#include  using namespace std; int countPair(int arr[], int n) { map m; for (int i = 0; i 

Java 实现

import java.util.*; class GFG { static int countPair(int[] arr, int n) { Map m = new HashMap<>(); for (int i = 0; i 

输出：5

时间复杂度：O(N log N)。

空间复杂度：O(N)。