Power Pokemon配对问题优化：解决重复元素及大测试用例失效问题

问题描述 #

Power Pokemon Couple指两只宝可梦的战力值之和为2的幂的组合。给定包含多只宝可梦战力值的数组power，计算可组成的此类配对数量。注意：不同索引的宝可梦即使战力值相同也视为不同个体，结果需对10^9+7取模。

约束条件：

• 1 ≤ power.length ≤ 10^5
• 0 ≤ power[i] ≤ 22

示例输入：

5
1 3 5 7 9

示例输出：4，对应配对为(1,3)、(1,7)、(3,5)、(7,9)，和分别为4、8、8、16（均为2的幂）。

原代码的问题分析 #

你提供的暴力解法存在两个核心问题：

1. 重复计算与自身配对：每对宝可梦会被计算两次（比如a和b，处理a时算b，处理b时算a），虽然最后除以2，但同时包含了宝可梦与自身配对的情况（比如数组[4,4,4,4]中，每个4会和自己配对一次，总共4次，导致最终结果多算了2）。
2. 效率冗余：使用HashMap存储频率对于固定范围（0-22）的战力值来说没必要，数组的访问效率更高。

以[4,4,4,4]为例，原代码计算过程：每个4在s=8时，key=4，累加freq.get(4)=4，4个元素共累加4*4=16，除以2得到8，但正确结果应为组合数C(4,2)=6，多出来的2就是因为包含了4次自身配对。

优化解决方案 #

由于战力值范围固定为0-22，我们可以用数组存储频率，然后遍历所有可能的2的幂，针对每个幂值计算有效配对数，避免重复和自身配对：

1. 统计频率：用大小为23的数组统计每个战力值出现的次数。
2. 遍历所有可能的2的幂：两个战力值的最大和为22+22=44，只需考虑2^0到2^5（即1、2、4、8、16、32），更大的2的幂（如64）的和无法由数组中的元素组成。
3. 计算配对数：
   • 对于每个幂值s，遍历每个战力值x：
     • 若x > s - x：跳过，避免重复计算配对。
     • 若x == s - x：计算组合数freq[x] * (freq[x]-1) / 2（从freq[x]个元素中选2个的组合数）。
     • 若x < s - x：计算freq[x] * freq[s - x]（两组元素的两两配对数）。
4. 取模处理：每次累加结果后对10^9+7取模，防止溢出。

优化后的Java代码 #

static int countPair(int[] power, int n) {
    final int MOD = 1000000007;
    // 战力值范围0-22，用数组存频率
    int[] freq = new int[23];
    for (int num : power) {
        freq[num]++;
    }

    long result = 0;
    // 遍历所有可能的2的幂：和的范围是0+0=0到22+22=44，所以2^0到2^5足够
    for (int i = 0; i <= 5; i++) {
        int s = 1 << i; // 等价于2^i，比Math.pow更高效且避免浮点误差
        for (int x = 0; x <= 22; x++) {
            int y = s - x;
            if (y < 0 || y > 22) {
                continue;
            }
            if (x > y) {
                continue; // 避免重复计算配对
            }
            if (x == y) {
                // 组合数C(freq[x], 2)
                long pairs = (long) freq[x] * (freq[x] - 1) / 2;
                result = (result + pairs) % MOD;
            } else {
                // 两组元素的两两配对数
                long pairs = (long) freq[x] * freq[y];
                result = (result + pairs) % MOD;
            }
        }
    }
    return (int) result;
}

代码解释 #

• 频率统计：用数组freq替代HashMap，访问时间复杂度O(1)，更适合固定范围的数值。
• 2的幂计算：用1 << i替代Math.pow，避免浮点运算带来的精度误差，效率更高。
• 配对计算逻辑：通过x <= y的判断，确保每对配对只计算一次，同时x == y时用组合数排除自身配对的情况。
• 数据类型：用long存储中间结果，防止整数溢出，最后再转成int返回。

测试[4,4,4,4]时，s=8（i=3），x=4，y=4，计算4*3/2=6，结果正确。测试示例输入时，最终结果为4，符合预期。

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