跳到主要内容

1711.大餐计数

链接：1711.大餐计数
难度：Medium
标签：数组、哈希表
简介：给你一个整数数组 deliciousness ，其中 deliciousness[i] 是第 i​​​​​​​​​​​​​​ 道餐品的美味程度，返回你可以用数组中的餐品做出的不同 大餐 的数量。

题解 1 - typescript​

  • 编辑时间：2021-07-07
  • 执行用时：304ms
  • 内存消耗：50.4MB
  • 编程语言：typescript
  • 解法介绍：对每个值进行查看 2 的幂可能性。
function countPairs(deliciousness: number[]): number {
  const MOD = 10 ** 9 + 7;
  const LIST_2: number[] = [];
  for (let i = 1, max = 2 ** 21; i <= max; i <<= 1) LIST_2.push(i);
  const map: Record<number, number> = {};
  let ans = 0;
  for (const num of deliciousness) {
    for (const num2 of LIST_2) if (num2 >= num) ans = (ans + (map[num2 - num] ?? 0)) % MOD;
    map[num] = (map[num] ?? 0) + 1;
  }
  return ans;
}