1711. 大餐计数

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
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);
    }
}