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

Hard

题目描述

给定一个整数数组 nums 和一个整数 k，返回 nums 中按位与值等于 k 的子数组数目。

示例 1：

输入：nums = [1,1,1], k = 1
输出：6
解释：所有子数组都只包含 1。

示例 2：

输入：nums = [1,1,2], k = 1
输出：3
解释：按位与值为 1 的子数组有：[1,1,2], [1,1,2], [1,1,2]。

示例 3：

输入：nums = [1,2,3], k = 2
输出：2
解释：按位与值为 2 的子数组有：[1,2,3], [1,2,3]。

约束条件：

1 <= nums.length <= 10^5
0 <= nums[i], k <= 10^9

提示：

假设我们要计算满足 nums[l] & nums[l + 1] & … & nums[r] == k 的对数 (l, r)。
固定左索引 l。
注意当固定 l 并增加 r 时，子数组的按位与值要么减少要么保持不变。
因此，考虑使用二分搜索。
要计算子数组的按位与值，使用稀疏表。

解题思路

这道题要求计算所有按位与值等于 k 的子数组数量。关键观察是：当我们固定左端点 l，从左到右扩展右端点 r 时，子数组的按位与值具有单调性——要么保持不变，要么变小（因为按位与操作只会清除位，不会设置位）。

主要思路：

单调性利用：对于固定的左端点 l，按位与值随着右端点增加而单调递减或保持不变。
二分搜索优化：利用单调性，我们可以用二分搜索快速找到：
- 第一个使得 AND(l, r) <= k 的位置
- 第一个使得 AND(l, r) < k 的位置
- 两者之间的区间就是所有 AND(l, r) == k 的右端点
稀疏表预处理：为了快速计算任意区间的按位与值，我们使用稀疏表进行预处理，使区间查询的时间复杂度降低到 O(1)。
算法流程：
- 构建稀疏表
- 对每个左端点 l，用二分搜索找到所有满足条件的右端点范围
- 累加所有可能的子数组数量

时间复杂度为 O(n log^2 n)，空间复杂度为 O(n log n)。

代码实现

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        int logn = 20; // log2(10^5) + 1
        
        // 构建稀疏表
        vector<vector<int>> st(n, vector<int>(logn));
        for (int i = 0; i < n; i++) {
            st[i][0] = nums[i];
        }
        
        for (int j = 1; j < logn; j++) {
            for (int i = 0; i + (1 << j) <= n; i++) {
                st[i][j] = st[i][j-1] & st[i + (1 << (j-1))][j-1];
            }
        }
        
        // 查询函数
        auto query = [&](int l, int r) -> int {
            int len = r - l + 1;
            int log_len = 31 - __builtin_clz(len);
            return st[l][log_len] & st[r - (1 << log_len) + 1][log_len];
        };
        
        long long result = 0;
        
        for (int l = 0; l < n; l++) {
            // 二分搜索找到第一个 AND 值 <= k 的位置
            int left = l, right = n - 1, first = -1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (query(l, mid) <= k) {
                    first = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            
            if (first == -1) continue;
            
            // 二分搜索找到第一个 AND 值 < k 的位置
            left = first, right = n - 1;
            int second = n;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (query(l, mid) < k) {
                    second = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            
            result += second - first;
        }
        
        return result;
    }
};

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        n = len(nums)
        logn = 20  # log2(10^5) + 1
        
        # 构建稀疏表
        st = [[0] * logn for _ in range(n)]
        for i in range(n):
            st[i][0] = nums[i]
        
        for j in range(1, logn):
            for i in range(n - (1 << j) + 1):
                st[i][j] = st[i][j-1] & st[i + (1 << (j-1))][j-1]
        
        def query(l, r):
            length = r - l + 1
            log_len = length.bit_length() - 1
            return st[l][log_len] & st[r - (1 << log_len) + 1][log_len]
        
        result = 0
        
        for l in range(n):
            # 二分搜索找到第一个 AND 值 <= k 的位置
            left, right, first = l, n - 1, -1
            while left <= right:
                mid = (left + right) // 2
                if query(l, mid) <= k:
                    first = mid
                    right = mid - 1
                else:
                    left = mid + 1
            
            if first == -1:
                continue
            
            # 二分搜索找到第一个 AND 值 < k 的位置
            left, right, second = first, n - 1, n
            while left <= right:
                mid = (left + right) // 2
                if query(l, mid) < k:
                    second = mid
                    right = mid - 1
                else:
                    left = mid + 1
            
            result += second - first
        
        return result

public class Solution {
    public long CountSubarrays(int[] nums, int k) {
        int n = nums.Length;
        int logn = 20; // log2(10^5) + 1
        
        // 构建稀疏表
        int[,] st = new int[n, logn];
        for (int i = 0; i < n; i++) {
            st[i, 0] = nums[i];
        }
        
        for (int j = 1; j < logn; j++) {
            for (int i = 0; i + (1 << j) <= n; i++) {
                st[i, j] = st[i, j-1] & st[i + (1 << (j-1)), j-1];
            }
        }
        
        int Query(int l, int r) {
            int len = r - l + 1;
            int logLen = 31 - LeadingZeroCount((uint)len);
            return st[l, logLen] & st[r - (1 << logLen) + 1, logLen];
        }
        
        long result = 0;
        
        for (int l = 0; l < n; l++) {
            // 二分搜索找到第一个 AND 值 <= k 的位置
            int left = l, right = n - 1, first = -1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (Query(l, mid) <= k) {
                    first = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            
            if (first == -1) continue;
            
            // 二分搜索找到第一个 AND 值 < k 的位置
            left = first;
            right = n - 1;
            int second = n;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (Query(l, mid) < k) {
                    second = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            
            result += second - first;
        }
        
        return result;
    }
    
    private int LeadingZeroCount(uint n) {
        if (n == 0) return 32;
        int count = 0;
        if (n <= 0x0000FFFF) { count += 16; n <<= 16; }
        if (n <= 0x00FFFFFF) { count += 8; n <<= 8; }
        if (n <= 0x0FFFFFFF) { count += 4; n <<= 4; }
        if (n <= 0x3FFFFFFF) { count += 2; n <<= 2; }
        if (n <= 0x7FFFFFFF) { count += 1; }
        return count;
    }
}

var countSubarrays = function(nums, k) {
    let count = 0;
    let n = nums.length;
    
    for (let i = 0; i < n; i++) {
        let currentAnd = nums[i];
        if (currentAnd === k) count++;
        
        for (let j = i + 1; j < n; j++) {
            currentAnd &= nums[j];
            if (currentAnd === k) {
                count++;
            } else if (currentAnd < k) {
                break;
            }
        }
    }
    
    return count;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度	说明
时间复杂度	O(n log²n)	稀疏表构建 O(n log n)，每个左端点进行两次二分搜索 O(log n)，总共 n 个左端点
空间复杂度	O(n log n)	稀疏表存储空间

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析