一、题目

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

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

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

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

点击查看原题
难度级别： 中等

二、思路

1）哈希表

直接想到暴力法的求解，就是使用O(n^2)时间复杂度进行遍历，把所有的组合都遍历一遍，就可以找到总的组合数量
为了减小时间复杂度，使用一个hashmap来寻找在遍历过的数中，是否存在一个数与当前数之和为2的幂次方，hashmap中的键为美味程度数值，值为已经遍历的同美味程度菜肴数量；且两数之和小于等于最大值*2

三、代码

1）哈希表

  1. class Solution {
  2.     public int countPairs(int[] deliciousness) {
  3.         long ans = 0;
  4.         Map<Integer, Integer> memo = new HashMap();
  5.         int maxVal = 0;
  6.         for (int i : deliciousness) {    // 找到最大值
  7.             maxVal = Math.max(maxVal, i);
  8.         }
  9.         maxVal <<= 1;
  10.         for (int val : deliciousness) {
  11.             for (int i = 1; i <= maxVal; i <<= 1) {
  12.                 if (i < val) {    // 本题两个数之和一定大于或等于单独数值的
  13.                     continue;
  14.                 }
  15.                 int needVal = i - val;
  16.                 ans = (ans + (long)memo.getOrDefault(needVal, 0)) %1000000007;
  17.             }
  18.             memo.put(val, memo.getOrDefault(val, 0) + 1);
  19.         }
  20.         return (int)ans;
  21.     }
  22. }

时间复杂度为O(nlogC)，C为最大值上限，空间复杂度为O(n)