题目描述
大餐 是指 恰好包含两道不同餐品 的一餐,其美味程度之和等于 2 的幂。
你可以搭配 任意 两道餐品做一顿大餐。
给定一个整数数组 deliciousness
,其中 deliciousness[i]
是第 i
道餐品的美味程度,返回你可以用数组中的餐品做出的不同 大餐 的数量。结果需要对 10^9 + 7
取余。
注意,只要餐品下标不同,就可以认为是不同的餐品,即便它们的美味程度相同。
样例
输入:deliciousness = [1,3,5,7,9]
输出:4
解释:大餐的美味程度组合为 (1,3) 、(1,7) 、(3,5) 和 (7,9) 。
它们各自的美味程度之和分别为 4 、8 、8 和 16 ,都是 2 的幂。
输入:deliciousness = [1,1,1,3,3,3,7]
输出:15
解释:大餐的美味程度组合为 3 种 (1,1) ,9 种 (1,3) ,和 3 种 (1,7) 。
限制
1 <= deliciousness.length <= 10^5
0 <= deliciousness[i] <= 2^20
算法
(哈希表) $O(n \log S)$
- 用哈希表统计每种数字出现的次数。
- 对于数字 $x$,枚举 2 的幂次,求出方案数。
- 最后通过除以 2 来去掉重复计算的部分。
时间复杂度
- 哈希表统计的时间复杂度为 $O(n)$。
- 对于每种数字,需要 $O(\log S)$ 的时间统计答案。其中 $S$ 为最大的数字。
- 故总时间复杂度为 $O(n \log S)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储哈希表。
C++ 代码
#define LL long long
class Solution {
public:
int countPairs(vector<int>& deliciousness) {
unordered_map<int, int> meals;
for (int x : deliciousness)
meals[x]++;
LL ans = 0;
for (const auto &m : meals)
for (int i = (1 << 21); i > 0 && i >= m.first; i >>= 1)
if (meals.find(i - m.first) != meals.end()) {
if (i == 2 * m.first)
ans += (LL)(m.second - 1) * m.second;
else
ans += (LL)(meals[i - m.first]) * m.second;
}
const int mod = 1000000007;
return ans / 2 % mod;
}
};
go
py3