1711. 大餐计数

这道题简单分析之后可以换一种说法就是“对数组中的不同数对进行两两组合，然后对组合的和为2的幂的组合进行计数”。
对于两两组合方法第一次的思路也比较简单，就是使用双重循环进行遍历组合，遍历的过程中对其求和判断是否是2的幂。
在这种思路下判断一个数是否是2的幂，采用的是位运算方法编写的代码。这种方法下的时间复杂度为1711 大餐计数 - 图1。

数组双重循环

  1. class Solution {
  2.     public int countPairs(int[] deliciousness) {
  3.         int cnt = 0;
  4.         int length = deliciousness.length;
  6.         for (int i = 0; i < length; i++) {
  7.             for (int j = i + 1; j < length; j++) {
  8.                 int cur = deliciousness[i] + deliciousness[j];
  9.                 if (isPowerOfTwo(cur)) {
  10.                     ++cnt;
  11.                 }
  12.             }
  13.         }
  15.         return cnt % 1000000007;
  16.     }
  18.     public boolean isPowerOfTwo(int n) {
  19.         return n > 0 && (n & (n - 1)) == 0;
  20.     }
  21. }

然而上面编写的代码在提交之后没有完全通过系统的测试，有部分用例超时了，通过查看用例发现这部分的用例中数组元素都非常长，而且存在重复的元素。因此，分析原因是在我编写的双重循环中出现了大量的重复计算（对于同一个元素，数组中存在多个元素与它的和为某个2的幂，这样每次计算导致了重复）。

哈希表去重

为了解决这个问题我们可以使用哈希表进行计数，将已经遍历的元素的个数使用哈希表保存下来，而在判断2的幂的这个问题上我们使用用2的幂的结果进行倒推（题目中数组元素都是有范围的，那么结果幂也必然是有范围的）。每个遍历到的数都会与前面出现过的数进行组合判断，这样相当于是从后向前组合来判断（第一种方法的双重循环是从前向后组合）。

  1. class Solution {
  2.     public int countPairs(int[] deliciousness) {
  3.         int ans = 0;
  4.         int maxVal = 0;
  5.         int MOD = 1000000007;
  7.         for (int delicious : deliciousness) {
  8.             if (delicious > maxVal) {
  9.                 maxVal = delicious;
  10.             }
  11.         }
  13.         int maxSum = maxVal * 2;
  15.         Map<Integer, Integer> map = new HashMap<>();
  17.         for (int i = 0; i < deliciousness.length; i++) {
  18.             int cur = deliciousness[i];
  20.             for (int sum = 1; sum <= maxSum; sum <<= 1) {
  21.                 int cnt = map.getOrDefault(sum - cur, 0);
  22.                 ans = (ans + cnt) % MOD;
  23.             }
  25.             map.put(cur, map.getOrDefault(cur, 0) + 1);
  26.         }
  28.         return ans;
  29.     }
  30. }

小结

  • 在数组中要进行两两组合的过程中，如果从前向后进行组合存在大量的重复，那么我们可以使用变为从当前的遍历向前进行组合，在这个过程中为了节省时间，可以将前面已经存在过的元素使用哈希表进行计数；
  • 对于结果需要取余这个要求在中间过程也需要进行考虑，因为中间的结果也可能溢出；
  • 注意题目中的提示，本题中已经提到数组的长度为1711 大餐计数 - 图2 ，那么两辆组合进行双重循环显然是不合适的，而每个元素在数组中是限定了范围的，因此可以从结果逆推，对于中间计数使用哈希表加快。