满足A[i]+A[j]=2^x的数组元素对计数问题排查与优化

问题描述 #

找出数组中满足以下条件的元素对(i,j)的数量：

1. i < j
2. A[i] + A[j] = 2^x（x为整数）
   结果需对10^9+7取模后返回。

约束条件 #

• 1 ≤ N ≤ 10^5
• 1 ≤ A[i] ≤ 10^9

你的代码存在的错误 #

1. int溢出导致死循环：
   你用int类型存储closePower，当key接近int最大值（如2^30=1073741824）时，closePower会溢出为负数，导致while(closePower <= key)循环无限执行，程序无法终止，这是导致部分测试用例失败的核心原因。

2. 未覆盖所有可能的2的幂（逻辑漏洞）：
   你的代码仅检查了第一个大于key的2的幂，但理论上key可以与多个不同补数组成不同的2的幂和。虽然在示例中这种方式能通过遍历补数间接统计，但逻辑上不完整，且依赖补数的遍历顺序，存在潜在漏统计风险（比如补数不存在时无影响，但代码逻辑不严谨）。

3. 潜在重复计数风险：
   若存在key和补数互为对方补数的情况，你的代码会在遍历两者时分别统计，导致结果翻倍。虽然在现有逻辑中因为仅检查第一个大于key的幂而未触发，但逻辑上存在重复计数的可能。

高效且正确的解决方案 #

核心思路 #

1. 哈希表统计频率：用哈希表存储每个元素的出现次数，O(N)时间复杂度完成统计。
2. 预生成所有可能的2的幂：由于A[i]≤1e9，最大和为2e9，预生成2^1到231的所有幂（共31个），覆盖所有可能的和。
3. 避免重复计数：遍历每个唯一元素时，仅统计补数大于当前元素的情况；补数等于当前元素时计算组合数；补数小于当前元素时跳过，确保每个元素对只被统计一次。
4. 使用long处理大数：避免计算过程中的溢出问题，保证数值正确性。

修正后的代码 #

import java.util.*;

public class Solution {
    private static final long MOD = 1000000007;
    // 预生成所有可能的2的幂，覆盖1e9+1e9的最大和范围
    private static final List<Long> POWERS = new ArrayList<>();
    static {
        long power = 2;
        for (int i = 1; i <= 31; i++) {
            POWERS.add(power);
            power *= 2;
        }
    }

    public static int twiceMatch(Integer[] A) {
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : A) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        long result = 0;
        for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
            int key = entry.getKey();
            int countKey = entry.getValue();
            boolean foundSame = false;
            for (long power : POWERS) {
                if (power <= key) {
                    continue; // 补数为非正数，无需考虑
                }
                long complementLong = power - key;
                if (complementLong > 1e9) {
                    continue; // 超出数组元素范围，直接跳过
                }
                int complement = (int) complementLong;
                if (!freqMap.containsKey(complement)) {
                    continue;
                }
                int countComplement = freqMap.get(complement);
                if (complement > key) {
                    // 统计不同元素的组合数，避免重复
                    result = (result + (long) countKey * countComplement) % MOD;
                } else if (complement == key) {
                    // 统计相同元素的组合数C(n,2)
                    long combinations = (long) countKey * (countKey - 1) / 2;
                    result = (result + combinations) % MOD;
                    foundSame = true;
                    break; // 同一元素只能对应一个满足条件的2的幂
                }
                // complement < key的情况跳过，后续遍历complement时会处理
            }
        }
        return (int) result;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        Integer[] A = new Integer[N];
        for (int j = 0; j < N; j++) {
            A[j] = scan.nextInt();
        }
        int result = twiceMatch(A);
        System.out.print(result);
    }
}

效率说明 #

• 时间复杂度：O(N + M*31)，其中M是数组中唯一元素的数量（M≤N），31是预生成的2的幂数量，整体接近O(N)，适合N=1e5的场景。
• 空间复杂度：O(M)，哈希表存储唯一元素的频率，空间占用可控。

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