Medium

题目描述

好数对 是指两个不同食物的美味程度之和等于2的幂次方的数对。

你可以选择任意两个不同的食物来制作好数对。

给你一个整数数组 deliciousness，其中 deliciousness[i] 是第 i 道食物的美味程度，返回你可以用这个列表做出的不同 好数对 的数量。结果需要对 10^9 + 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
解释：好数对为 (1,1) 有3种方式, (1,3) 有9种方式, 和 (1,7) 有3种方式。

提示：

  • 1 <= deliciousness.length <= 10^5
  • 0 <= deliciousness[i] <= 2^20

解题思路

这道题的关键在于理解什么是"好数对"：两个不同位置的食物，它们的美味程度之和等于2的幂次方。

核心思路： 由于 deliciousness[i] <= 2^20，两个元素的最大和为 2 * 2^20 = 2^21，所以我们只需要考虑从 2^0 到 2^21 这22个2的幂次方。

算法步骤：

  1. 使用哈希表记录每个美味程度的出现次数
  2. 对于每个可能的2的幂次方 target，遍历数组中的每个元素 x
  3. 检查 target - x 是否在哈希表中存在
  4. 如果存在，根据情况计算贡献的数对数量：
    • 如果 x == target - x，说明需要两个相同的数，贡献 count[x] * (count[x] - 1) / 2
    • 如果 x < target - x，贡献 count[x] * count[target - x]（避免重复计算）

注意事项：

  • 为避免重复计算，我们只在 x <= target - x 时进行计算
  • 当 x == target - x 时，需要特殊处理，因为是同一个数配对
  • 结果需要对 10^9 + 7 取余

这种方法的时间复杂度是 O(n + 22n) = O(n)，其中 n 是数组长度，远优于暴力的 O(n²) 方法。

代码实现

class Solution {
public:
    int countPairs(vector<int>& deliciousness) {
        const int MOD = 1e9 + 7;
        unordered_map<int, int> count;
        
        // 统计每个美味程度的出现次数
        for (int d : deliciousness) {
            count[d]++;
        }
        
        long long result = 0;
        
        // 遍历所有可能的2的幂次方
        for (int i = 0; i <= 21; i++) {
            int target = 1 << i;
            
            for (auto& [x, cnt] : count) {
                int y = target - x;
                
                if (count.count(y)) {
                    if (x == y) {
                        // 同一个数配对
                        result += (long long)cnt * (cnt - 1) / 2;
                    } else if (x < y) {
                        // 避免重复计算
                        result += (long long)cnt * count[y];
                    }
                }
            }
        }
        
        return result % MOD;
    }
};

class Solution:
    def countPairs(self, deliciousness: List[int]) -> int:
        MOD = 10**9 + 7
        from collections import Counter
        count = Counter(deliciousness)
        
        result = 0
        
        # 遍历所有可能的2的幂次方
        for i in range(22):
            target = 1 << i
            
            for x in count:
                y = target - x
                
                if y in count:
                    if x == y:
                        # 同一个数配对
                        result += count[x] * (count[x] - 1) // 2
                    elif x < y:
                        # 避免重复计算
                        result += count[x] * count[y]
        
        return result % MOD

public class Solution {
    public int CountPairs(int[] deliciousness) {
        const int MOD = 1000000007;
        var count = new Dictionary<int, int>();
        
        // 统计每个美味程度的出现次数
        foreach (int d in deliciousness) {
            count[d] = count.GetValueOrDefault(d, 0) + 1;
        }
        
        long result = 0;
        
        // 遍历所有可能的2的幂次方
        for (int i = 0; i <= 21; i++) {
            int target = 1 << i;
            
            foreach (var kvp in count) {
                int x = kvp.Key;
                int cnt = kvp.Value;
                int y = target - x;
                
                if (count.ContainsKey(y)) {
                    if (x == y) {
                        // 同一个数配对
                        result += (long)cnt * (cnt - 1) / 2;
                    } else if (x < y) {
                        // 避免重复计算
                        result += (long)cnt * count[y];
                    }
                }
            }
        }
        
        return (int)(result % MOD);
    }
}

var countPairs = function(deliciousness) {
    const MOD = 1000000007;
    const map = new Map();
    let result = 0;
    
    for (let d of deliciousness) {
        for (let power = 0; power <= 21; power++) {
            let target = (1 << power) - d;
            if (map.has(target)) {
                result = (result + map.get(target)) % MOD;
            }
        }
        map.set(d, (map.get(d) || 0) + 1);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n + 22k)，其中 n 是数组长度，k 是不同美味程度的数量。统计频次需要 O(n)，遍历22个2的幂次方和k个不同的数需要 O(22k)
空间复杂度O(k)，其中 k 是不同美味程度的数量，用于存储哈希表

相关题目