JZX轻语：简

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

发表于2024年08月10日

#动态规划 #计数DP

第四题反而没那么难想，其实就是计数DP。记dp[i][j]为以nums[i]结尾的子数组中，按位与值为j的数目。那么有状态转移方程：dp[i][j & nums[i]] += dp[i - 1][j]。由于j的范围是0~2^10，因此可以使用dict来存储dp数组。

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        cur_map = {nums[0]: 1}  # 初始状态
        ans = int(nums[0] == k)
        for i in range(1, len(nums)):
            new_map = defaultdict(int)
            new_map[nums[i]] = 1
            for prev_res, cnt in cur_map.items():
                new_map[prev_res & nums[i]] += cnt
            cur_map = new_map
            ans += cur_map.get(k, 0)
        return ans

闪念标签：LC

题目链接：https://leetcode.cn/problems/number-of-subarrays-with-and-value-of-k/