LeetCode 题解工作台
子数组按位与值为 K 的数目
给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中有多少个 子数组 满足：子数组中所有元素按位 AND 的结果为 k 。 示例 1： 输入： nums = [1,1,1], k = 1 输出： 6 解释： 所有子数组都只含有元素 1 。 示例 2： 输入： nums = [1,1,…
4
题型
5
代码语言
3
相关题
当前训练重点
困难 · 二分·搜索·答案·空间
答案摘要
根据题目描述，我们需要求出数组 下标 到 的元素的按位与运算的结果，即 $\textit{nums}[l] \land \textit{nums}[l + 1] \land \cdots \land \textit{nums}[r]$。其中 表示按位与运算。 如果我们每次固定右端点 ，那么左端点 的范围是 $[0, r]$。由于按位与之和随着 的减小而单调递减，并且 的值不超过 ，因…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中有多少个子数组满足：子数组中所有元素按位 AND 的结果为 k 。
示例 1：
输入：nums = [1,1,1], k = 1
输出：6
解释：
所有子数组都只含有元素 1 。
示例 2：
输入：nums = [1,1,2], k = 1
输出：3
解释：
按位 AND 值为 1 的子数组包括：[1,1,2], [1,1,2], [1,1,2] 。
示例 3：
输入：nums = [1,2,3], k = 2
输出：2
解释：
按位 AND 值为 2 的子数组包括：[1,2,3], [1,2,3] 。
提示：
1 <= nums.length <= 1050 <= nums[i], k <= 109
解题思路
方法一：哈希表 + 枚举
根据题目描述，我们需要求出数组 下标 到 的元素的按位与运算的结果，即 。其中 表示按位与运算。
如果我们每次固定右端点 ，那么左端点 的范围是 。由于按位与之和随着 的减小而单调递减，并且 的值不超过 ，因此区间 最多只有 种不同的值。因此，我们可以用一个集合来维护所有的 的值，以及这些值出现的次数。
当我们从 遍历到 时，以 为右端点的值，就是集合中每个值与 进行按位与运算得到的值，再加上 本身。
因此，我们只需要枚举集合中的每个值，与 进行按位与运算，就可以得到以 为右端点的所有值及其出现的次数。然后，我们还需要将 的出现次数加上去。此时，我们将值为 的出现次数累加到答案中。继续遍历 ，直到遍历完整个数组。
时间复杂度 ，空间复杂度 。其中 和 分别是数组 的长度和数组 中元素的最大值。
class Solution:
def countSubarrays(self, nums: List[int], k: int) -> int:
ans = 0
pre = Counter()
for x in nums:
cur = Counter()
for y, v in pre.items():
cur[x & y] += v
cur[x] += 1
ans += cur[k]
pre = cur
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Does the candidate identify binary search as a suitable strategy for optimizing the solution?
- question_mark
Can the candidate explain the handling of bitwise AND in the context of subarrays?
- question_mark
Is the candidate able to suggest multiple approaches, such as sliding window or prefix sums?
常见陷阱
外企场景- error
Not considering the bitwise operation as a way to efficiently handle large numbers.
- error
Failing to optimize the solution by applying binary search over the answer space.
- error
Overlooking the need for efficient data structures to track subarray AND values.
进阶变体
外企场景- arrow_right_alt
Alter the problem by changing the target AND value, k, for different subarray configurations.
- arrow_right_alt
Introduce additional constraints, such as limiting the size of the subarrays.
- arrow_right_alt
Require handling multiple arrays at once, each with a different k value.