零、写在前面

  这是《算法零基础100讲》 专栏打卡学习的第五天了，虽然有同学反馈一天一篇太难了，但是也有同学认为这样能够逼着他学习，很爽。任何一种模式，都不可能兼顾所有人，只有靠你自己去适应它，不断调整自己的学习方式，这就是 「 适者生存 」 的道理。
  我的算法零基础讲解，在前面几讲基本都是没有什么关联的，纯属野路子， 「 书上找不到 」 ，但是训练下来，可以锻炼你的思维能力。所以，就算某一章节落下了，也不要紧，只要坚持每天都打卡，就算漏了，后面也能够通过自己的悟性悟出来前面几章的内容，所以， 「 贵在坚持 」 ！
  也有同学是后面才加入的，希望你们不要气馁，当你开始要努力的时候，任何时间点开始都不会太迟，只要肯努力， 「 后来者居上 」 的例子不胜枚举。

一、概念定义

  今天要讲的方法很实用，名为计数法。
  计数法的含义顾名思义，就是利用一个变量，记录下某个数值出现了多少次。从而实现对数值的计数。例如，计算某个班级里面有多少学生智商大于 163，我们可以这么写：

int func(int *iq, int size) {
    int cnt = 0;
    for(i = 0; i < size; ++i) {
        if(iq[i] > 163) {
            ++cnt;
        }
    }
    return cnt;
}

  其中iq[]代表学生们的智商列表，我们把智商列表遍历一遍，然后统计大于 163 的，用一个变量cnt来计数，最后返回这个计数，这就是最简单的计数法。

  更深层次的，如果我们需要知道所有 IQ 值的分布，怎么来快速完成这个事情呢？沿用上面的方法，我们可以采用一个计数数组来完成这件事情。将 IQ 值 映射到数组的下标中，而数组值本身就对应了计数器的值。

int *func(int *iq, int size, int IQMax) {                // (1)
    int i;
    int *cnt = (int *)malloc( sizeof(int) * (IQMax+1) ); // (2)
    memset(cnt, 0, sizeof(int) * (IQMax+1));             // (3)
    for(i = 0; i < size; ++i) {
         ++cnt[ iq[i] ];                                 // (4)
    }
    return cnt;                                          // (5)
}

• $(1)$ 函数给定三个参数，分别代表一个 IQ数组，IQ数组的元素个数，最大的IQ值，要求返回一个数组，代表每个 IQ值 的人数有多少；
• $(2)$ cnt是一个区间范围为[0, IQMax]的计数器数组，其中cnt[i]代表 IQ值 为 $i$ 的学生人数；
• $(3)$ 初始化所有 IQ值 的学生人数都为 0；
• $(4)$ 遍历每个学生，找到对应的 IQ值 对应的计数器，执行自增操作，这种情况下，++cnt[ iq[i] ]和cnt[ iq[i] ]++是等价的；
• $(5)$ 返回计数器数组；

二、题目描述

  给定一个 $n(1 \le n \le 10^5)$ 个元素的整数数组 $a[i] (0 \le a[i] \le 2^{20})$，要求找出一些 “含有两个数” 的数对，并且这两个数的和为 2 的幂。求这样的数对的对数，如果超过 $10^9+7$，则返回除上 $10^9+7$ 后的余数。

三、算法详解

  如果用最暴力的算法，那就是从 $n$ 个数中找 2 个数，然后判断它们的和是否为 $2$ 的幂，如果是，则计数器加一。根据组合原理可得，总共有 $C_n^2$ 个数对需要判断，所以，这样做的算法时间复杂度为 $O(n^2)$ （其中 $C_n^m$ 为组合数）。
  那么，我们换个思路，观察数组的元素最大不会超过 $2^{20}$，也就是两个数加起来最大不会超过 $2^{21}$。所以，满足要求的数对，它们的加和一定是 $2^0$、 $2^1$、 $2^2$、 $...$、 $2^{21}$ 这 22 个数其中之一。
  于是，我们可以枚举其中一个数 $x$，再枚举它们的和 $sum$，那么另一个数一定是

$$other=sum-x$$

我们只要想办法找出 $other$ 的个数进行累加，返回这个累加值即可。
  这里的 $other$ 可以映射到数组下标，每次枚举完 $x$，我们可以对它执行自增操作，这样在下次统计的时候就可以通过数组下标在 $O(1)$ 的时间内获取它曾经出现过多少次。算法的时间复杂度为 $O(nc)$，其中 $c$ 为常数。

四、源码剖析

int cnt[ (1<<21) + 1 ];
int countPairs(int* deliciousness, int deliciousnessSize){
    int i, sum = 0;
    int ans = 0;
    memset (cnt, 0, sizeof(cnt));                    // (1)

    for(i = 0; i < deliciousnessSize; ++i) {         // (2)
        for(sum = 1; sum <= (1<<21); sum *= 2) {     // (3)
            other = sum - deliciousness[i];          // (4)
            if (other < 0) {                         // (5) 
                continue;
            }
            ans += cnt[ other ];                     // (6)
            ans %= 1000000007;
        }
        ++ cnt[ deliciousness[i] ];                  // (7)
    }
    return ans;                                      // (8)
}

• $(1)$ 初始化一个计数器数组，并且设定所有数出现次数均为 $0$；
• $(2)$ 枚举其中一个数；
• $(3)$ 两个数的和为2的幂，所以可以枚举所有的和；
• $(4)$ 这样就可以用减法计算出另一个数other；
• $(5)$ 如果另一个数小于0，则继续枚举另一个和；
• $(6)$ 否则cnt[other]里存的就是另一个数的数量，直接将方案数进行累加；
• $(7)$ 然后，把当前的这个数放入计数器中；
• $(8)$ 最后，返回ans为累加和；

五、推荐专栏

六、习题练习

请参考原文