Leetcode 1711. 大餐计数 哈希/位运算

原题链接：Leetcode 1711. 大餐计数

自己写的代码:

class Solution {
public:
    map<long long,long long> m;
    bool judge(int n)
    {
        return n>0 && (n&(n-1))==0;
    }
    int countPairs(vector<int>& deliciousness) {
        long long res=0,mod=1e9+7;
        for(auto num:deliciousness)  m[num]++;
        vector<int> del;
        sort(deliciousness.begin(),deliciousness.end());
        del.push_back(deliciousness[0]);
        for(auto num:deliciousness)
        {
            if(num!=del.back()) del.push_back(num);
        }
        for(auto num:del)
        {
            if(judge(num*2))  res=(res+(m[num]*(m[num]-1)/2)%mod)%mod;
            for(int i=0;i<=21;i++)
            {
                long long x=(1<<i);
                if(x-num>num) res=(res+(m[num]*m[x-num])%mod)%mod;
            }
        }
        return res;
    }
};

参考官解：Leetcode 1711. 大餐计数

class Solution {
public:
    int countPairs(vector<int>& deliciousness) {
        long long res=0;
        const int mod=1e9+7;
        unordered_map<int,int> m;
        int maxnum=*max_element(deliciousness.begin(),deliciousness.end());
        maxnum=maxnum*2;
        for(auto num:deliciousness)
        {
            for(int x=1;x<=maxnum;x<<=1)
            {
                int cnt=m.count(x-num) ? m[x-num]:0;
                res=(res+cnt)%mod;
            }
            m[num]++;
        }
        return res;
    }
};