1711. 大餐计数

细节满满的一题,组合计算问题再周赛的T3与T4经常出,对于常见的组合计算问题应该要掌握。

class Solution {
public int countPairs(int[] deliciousness) {
/*
HashMap+计数+容斥原理:
1 <= deliciousness.length <= 1e5
0 <= deliciousness[i] <= 2^20
看数据范围只能用O(N)、O(C*N)、O(NlogN)的时间复杂度算法进行求解
1.预处理出2的0~21次幂
2.HashMap统计每个数字出现的个数
3.枚举每个HashMap中的数字进行计数,以key为锚点,枚举所有的可能的二次幂并球出目标匹配数字;
之后先统计相同数字组成的对,再统计不同数字组成的对进行相加
4.最后记得对统计的数字/2
坑点:
1.2^0=1也是2的次幂
2.相同数字的计算方法为:num*(num-1)/2,其中num为数字个数
3.相同数字的计算方法为:cnt[t]*cnt[key]/2,其中t为要匹配的目标数字,key为当前数字
可以将2与3统一起来最后一起除2
4.这里long类型在统计过程中可以不进行MOD(<1e10),最后才取余即可
最好先进行除2操作最后再取余,如果顺序反了最后取余再除2结果不对!
还有最后取余的一定一定要把MOD括起来,否则就会将res先转换为int了!!!!
5.枚举二次幂可以倒序提前退出
*/
// 美味程度之和上限为2^21,预处理出2^0~2^21的幂
int cur = 1, MOD = (int) 1e9 + 7;
int[] arr = new int[22];
for (int i = 0; i <= 21; i++) {
arr[i] = cur;
cur *= 2;
}
// 统计数字对应个数
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : deliciousness) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
long res = 0L;
// 寻找每个数字缺失的另一半
for (int key : map.keySet()) {
long num = map.get(key); // 该数字key的数目
for (int i = 21; i >= 0; i--) {
int t = arr[i] - key; // 要找的目标数字
if (t < 0) break; // 从大的开始枚举,如果当前已经小于0,那么前面的必定小于0,提前break
// 1.先统计相同数字组成的:组合种数=cnt[key]*(cnt[key]-1)/2
if (t == key) {
res += num * (num - 1);
} else if (map.containsKey(t)) {
// 2.再统计不同数字之间的cnt[t]*cnt[key]/2
res += num * map.get(t);
}
}
}
// 最后统计重了一倍应该除2
return (int) ((res >> 1) % MOD);
}
}