大餐计数

难度: Medium

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

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

给你一个整数数组 deliciousness ，其中 deliciousness[i] 是第 i 道餐品的美味程度，返回你可以用数组中的餐品做出的不同大餐的数量。结果需要对 10⁹ + 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²⁰

Submission

运行时间: 96 ms

内存: 23.6 MB

class Solution:
    def countPairs(self, deliciousness: List[int]) -> int:
        MOD = 1000000007
        count = Counter(deliciousness)

        target, res = 1, 0
        for x in sorted(count):
            if x == 0:
                continue
            while target < x:
                target += target
            res += count[x] * count[target - x]
            if x == target:
                res += comb(count[x], 2)
        return res % MOD

Explain

本题解使用哈希表记录每个美味程度的出现次数，然后针对每个可能的美味程度组合，计算它们的和是否是2的幂。为了快速判断和是否是2的幂，算法首先对美味程度进行排序，然后使用一个循环，其中外层循环遍历每个不同的美味程度，内层循环则尝试匹配使得两个美味程度之和达到下一个2的幂。如果当前的美味程度与其匹配的美味程度相同，则需要使用组合数计算方式计算配对数目。这种方法利用了数学的组合逻辑以及哈希表的高效性能来解决问题。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def countPairs(self, deliciousness: List[int]) -> int:
        MOD = 1000000007
        count = Counter(deliciousness) # 计数每个美味程度出现的次数

        target, res = 1, 0
        for x in sorted(count): # 对美味程度进行排序
            if x == 0: # 0的情况单独处理
                continue
            while target < x: # 寻找下一个2的幂
                target += target
            res += count[x] * count[target - x] # 计算当前程度与目标程度的组合数
            if x == target: # 如果当前程度等于目标2的幂，计算组合数
                res += comb(count[x], 2)
        return res % MOD # 返回结果需要取模

Explore

使用哈希表来计数每个美味程度的出现次数在处理大量重复值时非常高效。哈希表（通常在Python中实现为字典）提供了平均O(1)时间复杂度的插入和查找操作。因此，当输入数据中存在大量重复项时，哈希表可以快速统计每个项的出现次数，不需要多次遍历整个数据集来计数，这大大提高了数据处理的速度。

对美味程度进行排序是必要的，因为这样可以更高效地寻找和为2的幂的组合。排序后，可以使用双指针或者二分搜索的方法来查找目标和，而不必对每个可能的组合进行遍历。此外，排序后的美味程度数组可以帮助算法快速跳过那些不可能满足条件的组合，从而减少不必要的计算和比较。

当两个美味程度相同的时候，我们需要计算这个程度值的项与自身配对的组合数。组合数可以通过数学公式C(n, 2) = n*(n-1)/2来计算，其中n是该美味程度的出现次数。这是因为每对不同的项都可以形成一个有效的配对。例如，如果一个美味程度出现了3次，那么可以形成3*(3-1)/2 = 3种不同的配对。这种情况通常出现在美味程度的值与目标2的幂相等时，因为只有美味程度相等的情况下，两者之和才会等于一个2的幂。

在计算组合数并进行模运算时，应注意以下几点编程细节：首先，当计算组合数C(n, 2) = n*(n-1)/2时，为了避免在乘法操作中产生溢出，应该先对n和(n-1)中的至少一个数进行MOD运算。其次，由于MOD是一个很大的质数，可以使用费马小定理来计算除法的模逆元，以便在模运算的环境下执行除法。此外，在实际编程实现中，还应当注意整数除法可能引入的舍入误差，确保所有的运算都在整数域中进行。