大餐计数

使用哈希表存储数组中的每个元素的出现次数，遍历到数组 deliciousness 中的某个元素时，在哈希表中寻找与当前元素的和等于 2 的幂的元素个数，然后用当前元素更新哈希表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  const int mod = 1e9 + 7;
  int countPairs(vector<int>& d) {
    int maxVal = *max_element(d.begin(), d.end());
    int maxSum = maxVal * 2;
    int pairs = 0;
    unordered_map<int, int> mp;
    int n = d.size();
    for (auto& val : d) {
      for (int sum = 1; sum <= maxSum; sum <<= 1) {
        int count = mp.count(sum - val) ? mp[sum - val] : 0;
        pairs = (pairs + count) % mod;
      }
      mp[val]++;
    }
    return pairs;
  }
};