3209. 子数组按位与值为 K 的数目

题目描述

给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中有多少个子数组满足：子数组中所有元素按位 AND 的结果为 k

思路1:动态规划

打力扣打PTSD了，看什么题都是DP

状态：dp[i][j]表示以num[i]结尾，二进制第j位连续是1的最长长度

状态转移：

如果nums[i]的第j是1，则dp[i][j] = dp[i - 1][j] + 1
否则，dp[i][j] = 0

有了状态以后，怎么计算答案？

我们可以枚举子数组的右边界 i ，然后想办法去计算左边界的一个上界和下界

如果k的第j位是1，根据&运算的性质，则满足条件的子数组的每个数的第j位都应该是1。所以我们对k的每一个是1的位，求对应dp[i][j]的最小值，计作minx，求最小值的原因是，我们要求出满足这个子区间所有k是1的位都是1的最短长度，这是上界，不能再往前找了，因为只要再往前一位，一定存在一位本该是1的位置&上了0，变成了0，使得区间&起来不是k
如果k的第j位是0，根据&运算的性质，则满足条件的子数组的第j位应该至少有一个0，所以我们对k的每一个是0的位，求对应dp[i][j]的最大值，计作maxn，求最大值的原因是，dp[i][j]代表第nums[i]的第j位往前连续的1的最长长度，我们现在要保证有一个0，则往前的第一个0是位于往前dp[i][j]+1的位置，这是下界，是可以再往前找的，因为前面不管是什么，我们是0的位置&起来都是0
所以答案就是 max(0, minx - maxn)

对于每个右边界i,我们都算出maxn和minx，求个 \sum{max(0, minx-main)}就行

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        vector<vector<int>>dp(n + 1, vector<int>(32));
        long long ans = 0;
        for(int i = 1; i <= nums.size(); ++i){
            for(int j = 0; j < 32; ++j){
                if((nums[i - 1]>>j) & 1)dp[i][j] = dp[i - 1][j] + 1;
                else dp[i][j] = 0;
            }
            int minx = i, maxn = 0;
            for(int j = 0; j < 32; ++j){
                if((k>>j)&1)minx = min(minx, dp[i][j]);
                else maxn = max(maxn, dp[i][j]);
            }
            cout<< minx << " " << maxn << endl;
            ans += max(0, minx - maxn);
        }
        return ans;
    }
};

思路2:位运算性质+二分

考虑一个简单问题，给定一个数组，如何求所有（子区间num[i]到 $num\[j\]$ 进行与操作后起来）的结果

我们可以对数组进行如下操作：

我们搞一个new\_num数组，初始new\_num[i]=num[i]
然后i从1开始遍历到n，j从i-1遍历到1，每次都把new_num[i]与前面所有的 $num\[j\]$ 进行与操作，即new\_num[j] = new\_num[j]\& num[i]
这样操作会使得每次遍历完i，会使得new\_num[j]变成num[j]\&num[j+1]\&…\&num[i]
在这个过程中就可以得到所有的子区间数字相与的结果

但是如果仅仅是这样做，只会是标准的O(n^2)复杂度，我们可以想办法优化一下

由于&操作，一定会让数字变小或者不变，所以我们在第二层枚举的时候，可以判断一下如果new\_num[j]==new\_num[j]\&num[i]，说明

也就是说\&上num[i]不会使得new\_num[j]变小，那我们就可以停止第二层的循环了

我们可以将&操作看作集合的求交集操作，现在new\_num[j]==new\_num[j]\&num[i]说明new\_num[j]二进制是1的位置的集合一定是num[i]二进制是1的位置的集合的子集，而因为new\_num[j - 1] = new\_num[j] \& num[j-1]，则new\_num[j-1]<=new\_num[j]，new\_num[j-1]二进制是1的位置的集合一定是new\_num[j]二进制是1的位置的集合的子集，则集合的大小关系是new\_num[j - 1]\subseteq{new\_num[j]}\subseteq{num[i]}

那这样new\_num[j-1]&上num[i]也一定不变，当然，不是说只有j-1不用&了，小于j-1的也不用&了，证明同上

可以发现，如果想让数字变小，一定是至少有一位二进制位从1变成0，由于本题二进制下1最多30位，所以最坏的时间也就是O(n*log(max_element))

现在回到本题，本题求的是子区间&起来等于k的数量，我们只需要在循环i的时候，统计一下1到i中num[i]=k的数量，求和就行，num[i]中数字都是连续出现且递增的，所以我们可以用二分来找

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        long long ans = 0;
        for(int i = 0; i < n; ++i){
            for(int j = i - 1; j >= 0; --j){
                if((nums[j] & nums[i]) == nums[j]){
                    break;
                }
                nums[j] &= nums[i];
            }
            int l = lower_bound(nums.begin(), nums.begin() + i + 1, k) - nums.begin();
            int r = upper_bound(nums.begin(), nums.begin() + i + 1, k) - nums.begin();
            ans += r - l;
        }
        return ans;
    }
};