【leetcode】1711. 大餐计数（count-good-meals）（二分）[中等]

链接

https://leetcode-cn.com/problems/count-good-meals/

耗时

解题：5 h 16 min
题解：38 min

题意

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

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

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

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

提示：

• 1 <= deliciousness.length <= 105
• 0 <= deliciousness[i] <= 220

思路

我认为这就是有多个 target 的 【leetcode】1. 两数之和（two-sum）（模拟）[简单] 并且答案有很多种，返回答案的数量。看数据范围，target 最大不会超过 2 21 2^{21} 221 所以枚举出 0 到 22 所有的 2 的幂即是所有可能的 target。

然后计数每个元素的数量，再将唯一的美味值排序，排序是为了不重复计数。

最后 直接使用 哈希表 或者 二分查找元素是否存在，有则将对应的数量相乘计数即可。

时间复杂度： O ( 23 ∗ n l o g n ) O(23*nlogn) O(23∗nlogn)

AC代码

哈希

class Solution {
public:
    int countPairs(vector<int>& deliciousness) {
        // 2 的幂(0--22)
        vector<int> target;
        int x = 1;
        for(int i = 0; i < 23; ++i) {
            target.push_back(x);
            x <<= 1;
        }
        
        // 计数每个元素的数量
        unordered_map<int, int> delic_num;
        for(auto delic : deliciousness) {
            if(delic_num.find(delic) != delic_num.end()) {
                delic_num[delic]++;
            }
            else {
                delic_num[delic] = 1;
            }
        }
        
        // 唯一美味值
        vector<int> unique_deliciousness;
        for(auto delic : delic_num) {
            unique_deliciousness.push_back(delic.first);
        }
        
        sort(unique_deliciousness.begin(), unique_deliciousness.end());
        
        // 哈希 计数 大餐数
        int ans = 0;
        int MOD = 1000000007;
        for(auto tar : target) {
            if(tar > 2*unique_deliciousness[unique_deliciousness.size()-1]) {
                break;
            }
            for(auto delic : unique_deliciousness) {
                if(delic >  tar-delic) break;
                if(delic == tar-delic) {
                    int x = delic_num[delic];
                    ans += ((((long long)x*((long long)x-1))/2) % MOD);
                }
                else {
                    if(!delic_num[tar-delic]) continue; 
                    ans += (((long long)delic_num[delic]*(long long)delic_num[tar-delic]) % MOD);
                }
            }
            ans %= MOD;
        }
        
        return ans;        
    }
};

二分

class Solution {
public:
    int countPairs(vector<int>& deliciousness) {
        // 2 的幂(0--22)
        vector<int> target;
        int x = 1;
        for(int i = 0; i < 23; ++i) {
            target.push_back(x);
            x <<= 1;
        }
        
        // 计数每个元素的数量
        unordered_map<int, int> delic_num;
        for(auto delic : deliciousness) {
            if(delic_num.find(delic) != delic_num.end()) {
                delic_num[delic]++;
            }
            else {
                delic_num[delic] = 1;
            }
        }
        
        // 唯一美味值
        vector<int> unique_deliciousness;
        for(auto delic : delic_num) {
            unique_deliciousness.push_back(delic.first);
        }
        
        sort(unique_deliciousness.begin(), unique_deliciousness.end());
        
        // 二分 计数 大餐数
        int ans = 0;
        int MOD = 1000000007;
        for(auto tar : target) {
            if(tar > 2*unique_deliciousness[unique_deliciousness.size()-1]) {
                break;
            }
            for(auto delic : unique_deliciousness) {
                if(delic >  tar-delic) break;
                if(delic == tar-delic) {
                    int x = delic_num[delic];
                    ans += ((((long long)x*((long long)x-1))/2) % MOD);
                }
                else {
                    auto pos = lower_bound(unique_deliciousness.begin(), unique_deliciousness.end(), tar-delic);
                    if(pos == unique_deliciousness.end() || *pos != tar-delic) continue;
                    ans += (((long long)delic_num[delic]*(long long)delic_num[tar-delic]) % MOD);
                }
            }
            ans %= MOD;
        }
        
        return ans;        
    }
};