Java实现：统计数组中满足Ai+Aj=2^x的(i,j)对数（i<j）

给定长度为N的整数数组A，找出满足i<j且Ai + Aj = 2^x（x为整数）的索引对(i,j)的数量，结果需对10^9+7取模。需实现twiceMatch函数，接收数组A并返回符合条件的对数。

约束条件 #

• 1 ≤ N ≤ 10^5
• 1 ≤ Ai ≤ 10^9

常见错误点排查 #

1. 幂次范围不足：由于两个Ai的和最大为2×10^9，对应的2^x最大为2^31（2147483648），若遍历的x范围未覆盖1到31，会漏掉部分合法组合。
2. 重复计数：直接遍历数组查找补数时，会将(i,j)和(j,i)重复统计，需通过哈希表频率统计+组合数计算避免。
3. 整数溢出：计算2^x时用int类型会溢出，必须用long存储幂次结果。
4. 同数组合错误计算：当Ai = 2^(x-1)时，Ai+Ai=2^x，此时应计算组合数C(count,2)=count*(count-1)/2，而非count*count。

修正后的Java代码 #

import java.util.HashMap;
import java.util.Map;

public class Solution {
    private static final int MOD = 1000000007;

    public int twiceMatch(int[] A) {
        Map<Long, Integer> freqMap = new HashMap<>();
        // 统计数组中每个数字的出现频率
        for (int num : A) {
            long val = (long) num;
            freqMap.put(val, freqMap.getOrDefault(val, 0) + 1);
        }

        long result = 0;
        // 遍历所有可能的2的幂次（x从1到31，覆盖所有可能的两数之和范围）
        for (int x = 1; x <= 31; x++) {
            long target = 1L << x;
            // 临时拷贝哈希表避免并发修改异常
            Map<Long, Integer> tempMap = new HashMap<>(freqMap);
            
            for (Map.Entry<Long, Integer> entry : tempMap.entrySet()) {
                long num = entry.getKey();
                int count = entry.getValue();
                if (count == 0) continue;

                long complement = target - num;
                if (!freqMap.containsKey(complement)) continue;

                int complementCount = freqMap.get(complement);
                if (num == complement) {
                    // 同数组合：计算C(count,2)
                    result = (result + (long) count * (count - 1) / 2) % MOD;
                    freqMap.put(num, 0); // 标记已处理，避免重复统计
                } else if (num < complement) {
                    // 异数组合：直接相乘频率
                    result = (result + (long) count * complementCount) % MOD;
                    freqMap.put(num, 0);
                    freqMap.put(complement, 0); // 标记两者已处理
                }
            }
        }
        return (int) (result % MOD);
    }
}

代码说明 #

1. 频率统计：用哈希表记录每个数字的出现次数，避免重复遍历原数组，提升时间效率。
2. 幂次遍历：覆盖x从1到31的所有可能，确保不遗漏任何合法的2^x目标值。
3. 去重处理：通过标记已处理的数字，确保每对合法索引仅被统计一次。
4. 组合数计算：针对同数相加的场景，使用组合数公式计算正确对数，避免重复计数。
5. 模运算控制：每次计算结果后立即对10^9+7取模，防止数值溢出。

内容的提问来源于stack exchange，提问作者Fibin pious