2021-7-7每日一题

原题链接：https://leetcode-cn.com/problems/count-good-meals/
思路1：暴力解法两重循环遍历，超时
思路2（太菜了没想到）：通过hash表优化查询，使得只需要一重循环就够了。
比如：1,3,5,7,9，通过hash表记录每个数出现的次数。
初始ans = 0;
1：依次检查1,2,4,8…2^21，1>=2^0，检查hash[2^0 - 1]（两数和等于2的幂次，那就看存不存在另一个数相加使得和为2的幂次），不存在，ans = 0，hash[1]++（结果为1）
3: 检查到2^2，hash[2^2 - 3] = 1，因此加上数组中1的个数，ans + hash[1] = 1;
同理，5,7,9；

实现：

class Solution {
public:
    int countPairs(vector<int>& deliciousness) {
        unordered_map<int, int> mp;
        int len = deliciousness.size();
        int ans = 0, mod = 1e9+7, maxSum = 0;
        for(int i = 0 ;i < len; i++)maxSum = max(maxSum, deliciousness[i]);
        maxSum <<= 1;
        for(int i = 0; i < len; i++){
            int twoSum = 1, n = deliciousness[i];
            for(; twoSum <= maxSum; twoSum <<= 1){
                if(twoSum >= n){
                    ans += mp[twoSum - n];
                    ans %= mod;
                }
            }
            mp[n] ++;
        }
        return ans;
    }
};