leetcode 1711. 大餐计数

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

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

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

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

package com.example.lettcode.hashtable;

import java.util.HashMap;
import java.util.Map;

/**
 * @Class CountPairs
 * @Description 1711. 大餐计数
 * @Author
 * @Date 2021/7/7
 **/
public class CountPairs {
    public static int countPairs(int[] deliciousness) {
        if (deliciousness == null || deliciousness.length == 0) return 0;

        final int MOD = 1000000007;
        int len = deliciousness.length;
        Map<Integer, Integer> integerMap = new HashMap<>();
        int maxValue = 0;
        // 获取数组元素的上限
        for (int i = 0; i < len; i++) {
            maxValue = Math.max(maxValue, deliciousness[i]);
        }
        // 一对元素和的上限
        int maxSum = maxValue * 2;
        // 对数
        int pairs = 0;
        for (int i = 0; i < len; i++) {
            int value = deliciousness[i];
            // 因为求和是某数的幂，不需要采用自增的方式
            for (int sum = 1; sum <= maxSum; sum <<= 1) {
                // 统计与value之和等于sum的元素个数
                int count = integerMap.getOrDefault(sum - value, 0);
                pairs = (pairs + count) % MOD;
            }
            integerMap.put(value, integerMap.getOrDefault(value, 0) + 1);
        }
        return pairs;
    }

}

// 测试用例
public static void main(String[] args) {
    int[] deliciousness = new int[]{1,3,5,7,9};
    int pairs = CountPairs.countPairs(deliciousness);
    System.out.println("CountPairs demo01 result : " + pairs);

    deliciousness = new int[]{1,1,1,3,3,3,7};
    pairs = CountPairs.countPairs(deliciousness);
    System.out.println("CountPairs demo02 result : " + pairs);

    deliciousness = new int[]{64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64};
    pairs = CountPairs.countPairs(deliciousness);
    System.out.println("CountPairs demo03 result : " + pairs);
}