Leetcode_1711. 大餐计数

【原题链接】

1711. 大餐计数

【题目描述】

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

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

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

【代码】

class Solution {
public:
    int countPairs(vector<int>& deliciousness) {
        int res = 0, N = 1e9 + 7;
        unordered_map<int, int> mp;
        for(auto x : deliciousness){
            for(int i = 0; i <= 21; i++){
                int j = (1 << i) - x;
                if(mp.count(j)) res = (res + mp[j]) % N;
            }
            mp[x] ++;
        }
        return res;
    }
};

执行用时: 1200 ms

内存消耗: 57 MB

【时间复杂度】

O(21*n^2)

【注意点】

  1. 其他解法:开连续空间,存储各个数字是否存在
  2. 注意,若不加mp.count(j), 会超时,因为运行mp[j]会默认创建节点。

评论