1711. 大餐计数Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

大餐是指恰好包含两道不同餐品的一餐，其美味程度之和等于 2 的幂。

你可以搭配任意两道餐品做一顿大餐。

给你一个整数数组 deliciousness ，其中 deliciousness[i] 是第 i 道餐品的美味程度，返回你可以用数组中的餐品做出的不同大餐的数量。结果需要对 109 + 7 取余。

注意，只要餐品下标不同，就可以认为是不同的餐品，即便它们的美味程度相同。

示例 1：

输入：deliciousness = [1,3,5,7,9]
输出：4
解释：大餐的美味程度组合为 (1,3) 、(1,7) 、(3,5) 和 (7,9) 。
它们各自的美味程度之和分别为 4 、8 、8 和 16 ，都是 2 的幂。

示例 2：

输入：deliciousness = [1,1,1,3,3,3,7]
输出：15
解释：大餐的美味程度组合为 3 种 (1,1) ，9 种 (1,3) ，和 3 种 (1,7) 。

提示：

1 <= deliciousness.length <= 10⁵
0 <= deliciousness[i] <= 2²⁰

# 思路

枚举右维护左

# 解法



class Solution {
    public static final int MOD = 1_000_000_007;

    public int countPairs(int[] deliciousness) {
        int ans = 0;

        // 存储 2 的幂的集合，用于后续判断两餐美味程度之和是否为 2 的幂
        Set<Integer> set = new HashSet<>();

        // 生成 2 的 0 到 21 次幂并添加到集合中
        // 到 21 次幂，题目中 0 <= deliciousness[i] <= 2^20，两数相加最大接近 2^21
        for (int i = 0; i <= 21; i++) {
            set.add(1 << i);
        }

        // 存储每个美味程度出现的次数，要维护的“左”部分
        Map<Integer, Integer> map = new HashMap<>();

        // 遍历过程就是枚举“右”元素
        // 即当前正在处理的元素，通过与之前记录的“左”元素组合来判断是否构成大餐
        for (int num : deliciousness) {

            // 遍历所有 2 的幂
            for (int power : set) {
                // 检查当前 2 的幂减去当前餐的美味程度的差值是否已经在之前出现过
                // 若存在于 map 中，说明之前有“左”元素能和当前的“右”元素 num 组成美味程度之和为 2 的幂的大餐
                if (map.containsKey(power - num)) {
                    // 累加满足条件的组合数，并对结果取模
                    // 因为 map 中存储的是之前出现过的元素的出现次数
                    // 所以将其累加到结果中，表示当前“右”元素与之前这些“左”元素能构成的大餐组合数量
                    ans = (ans + map.get(power - num)) % MOD;
                }
            }
            // 更新当前美味程度的出现次数
            // 将当前“右”元素纳入“左”的范畴，维护 map 中元素及其出现次数
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        return ans;
    }
}

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

# 总结

分析出几种情况，然后分别对各个情况实现

#Java