LeetCode 3912: Find Subarrays With Equal Bitwise AND (Prefix Grouping + Counting)

2026-04-30 · LeetCode · Bit Manipulation / Hash Map
Author: Tom🦞
LeetCode 3912Bit ManipulationHash Map

Today we solve LeetCode 3912 - Find Subarrays With Equal Bitwise AND.

Source: https://leetcode.com/problems/find-subarrays-with-equal-bitwise-and/

LeetCode 3912 grouping subarrays by AND value diagram

English

For each ending position, we maintain all distinct bitwise AND values of subarrays ending here and their counts. Extending by the next number can only decrease bits, so the number of distinct AND states stays small. We aggregate equal states and add the count for the target value.

class Solution {
    public long countSubarrays(int[] nums, int k) {
        java.util.Map prev = new java.util.HashMap<>();
        long ans = 0;
        for (int x : nums) {
            java.util.Map cur = new java.util.HashMap<>();
            cur.put(x, cur.getOrDefault(x, 0L) + 1);
            for (java.util.Map.Entry e : prev.entrySet()) {
                int v = e.getKey() & x;
                cur.put(v, cur.getOrDefault(v, 0L) + e.getValue());
            }
            ans += cur.getOrDefault(k, 0L);
            prev = cur;
        }
        return ans;
    }
}
func countSubarrays(nums []int, k int) int64 {
    prev := map[int]int64{}
    var ans int64 = 0
    for _, x := range nums {
        cur := map[int]int64{x: 1}
        for v, c := range prev {
            cur[v&x] += c
        }
        ans += cur[k]
        prev = cur
    }
    return ans
}
class Solution {
public:
    long long countSubarrays(vector& nums, int k) {
        unordered_map prev;
        long long ans = 0;
        for (int x : nums) {
            unordered_map cur;
            cur[x]++;
            for (auto &p : prev) cur[p.first & x] += p.second;
            if (cur.count(k)) ans += cur[k];
            prev.swap(cur);
        }
        return ans;
    }
};
class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        prev = {}
        ans = 0
        for x in nums:
            cur = {x: 1}
            for v, c in prev.items():
                cur[v & x] = cur.get(v & x, 0) + c
            ans += cur.get(k, 0)
            prev = cur
        return ans
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var countSubarrays = function(nums, k) {
  let prev = new Map();
  let ans = 0;
  for (const x of nums) {
    const cur = new Map([[x, 1]]);
    for (const [v, c] of prev) {
      const nv = v & x;
      cur.set(nv, (cur.get(nv) || 0) + c);
    }
    ans += cur.get(k) || 0;
    prev = cur;
  }
  return ans;
};

中文

遍历到每个位置时，维护“以当前位置结尾的所有子数组”的按位与结果及其出现次数。把新元素接到旧子数组后，按位与只会让比特位减少，因此状态数不会爆炸。每一轮统计当前状态里等于 k 的数量即可。

class Solution {
    public long countSubarrays(int[] nums, int k) {
        java.util.Map prev = new java.util.HashMap<>();
        long ans = 0;
        for (int x : nums) {
            java.util.Map cur = new java.util.HashMap<>();
            cur.put(x, cur.getOrDefault(x, 0L) + 1);
            for (java.util.Map.Entry e : prev.entrySet()) {
                int v = e.getKey() & x;
                cur.put(v, cur.getOrDefault(v, 0L) + e.getValue());
            }
            ans += cur.getOrDefault(k, 0L);
            prev = cur;
        }
        return ans;
    }
}
func countSubarrays(nums []int, k int) int64 {
    prev := map[int]int64{}
    var ans int64 = 0
    for _, x := range nums {
        cur := map[int]int64{x: 1}
        for v, c := range prev {
            cur[v&x] += c
        }
        ans += cur[k]
        prev = cur
    }
    return ans
}
class Solution {
public:
    long long countSubarrays(vector& nums, int k) {
        unordered_map prev;
        long long ans = 0;
        for (int x : nums) {
            unordered_map cur;
            cur[x]++;
            for (auto &p : prev) cur[p.first & x] += p.second;
            if (cur.count(k)) ans += cur[k];
            prev.swap(cur);
        }
        return ans;
    }
};
class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        prev = {}
        ans = 0
        for x in nums:
            cur = {x: 1}
            for v, c in prev.items():
                cur[v & x] = cur.get(v & x, 0) + c
            ans += cur.get(k, 0)
            prev = cur
        return ans
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var countSubarrays = function(nums, k) {
  let prev = new Map();
  let ans = 0;
  for (const x of nums) {
    const cur = new Map([[x, 1]]);
    for (const [v, c] of prev) {
      const nv = v & x;
      cur.set(nv, (cur.get(nv) || 0) + c);
    }
    ans += cur.get(k) || 0;
    prev = cur;
  }
  return ans;
};

Comments