LeetCode 题解工作台
或值至少为 K 的最短子数组 II
给你一个 非负 整数数组 nums 和一个整数 k 。 如果一个数组中所有元素的按位或运算 OR 的值 至少 为 k ，那么我们称这个数组是 特别的 。 请你返回 nums 中 最短特别非空 子数组 的长度，如果特别子数组不存在，那么返回 -1 。 示例 1： 输入： nums = [1,2,3],…
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 滑动窗口（状态滚动更新）
答案摘要
我们可以发现，如果我们固定子数组的左端点，随着右端点向右移动，子数组的按位或值只会增大，不会减小。因此我们可以使用双指针的方法，维护一个满足条件的子数组。 具体地，我们使用两个指针 和 分别表示子数组的左右端点，初始时两个指针都位于数组的第一个元素。用一个变量 表示子数组的按位或值，初始时 的值为 。我们还需要维护一个长度为 的数组 ，表示子数组中每个元素的二进制表示中每一位的出现次数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 滑动窗口（状态滚动更新） 题型思路
题目描述
给你一个 非负 整数数组 nums 和一个整数 k 。
如果一个数组中所有元素的按位或运算 OR 的值 至少 为 k ，那么我们称这个数组是 特别的 。
请你返回 nums 中 最短特别非空 子数组的长度，如果特别子数组不存在，那么返回 -1 。
示例 1：
输入：nums = [1,2,3], k = 2
输出：1
解释：
子数组 [3] 的按位 OR 值为 3 ，所以我们返回 1 。
示例 2：
输入：nums = [2,1,8], k = 10
输出：3
解释：
子数组 [2,1,8] 的按位 OR 值为 11 ，所以我们返回 3 。
示例 3：
输入：nums = [1,2], k = 0
输出：1
解释：
子数组 [1] 的按位 OR 值为 1 ，所以我们返回 1 。
提示：
1 <= nums.length <= 2 * 1050 <= nums[i] <= 1090 <= k <= 109
解题思路
方法一：双指针 + 计数
我们可以发现，如果我们固定子数组的左端点，随着右端点向右移动，子数组的按位或值只会增大，不会减小。因此我们可以使用双指针的方法，维护一个满足条件的子数组。
具体地，我们使用两个指针 和 分别表示子数组的左右端点，初始时两个指针都位于数组的第一个元素。用一个变量 表示子数组的按位或值，初始时 的值为 。我们还需要维护一个长度为 的数组 ，表示子数组中每个元素的二进制表示中每一位的出现次数。
在每一步操作中，我们将 向右移动一位，更新 和 。如果 的值大于等于 ，我们不断更新子数组的最小长度，并将 向右移动一位，直到 的值小于 。在这个过程中，我们也需要更新 和 。
最后，我们返回最小长度，如果不存在满足条件的子数组，则返回 。
时间复杂度 ，空间复杂度 ，其中 和 分别是数组的长度和数组中元素的最大值。
相似题目：
class Solution:
def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
n = len(nums)
cnt = [0] * 32
ans = n + 1
s = i = 0
for j, x in enumerate(nums):
s |= x
for h in range(32):
if x >> h & 1:
cnt[h] += 1
while s >= k and i <= j:
ans = min(ans, j - i + 1)
y = nums[i]
for h in range(32):
if y >> h & 1:
cnt[h] -= 1
if cnt[h] == 0:
s ^= 1 << h
i += 1
return -1 if ans > n else ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Look for familiarity with sliding window and bitwise manipulation techniques.
- question_mark
Assess the ability to optimize a brute-force approach into an efficient solution.
- question_mark
Check for understanding of deque usage in maintaining a sliding window of indices.
常见陷阱
外企场景- error
Not updating the OR value incrementally and recalculating it for each subarray.
- error
Failing to shrink the window when the OR value meets or exceeds k.
- error
Incorrectly handling edge cases, such as when no valid subarray exists.
进阶变体
外企场景- arrow_right_alt
What if the problem asked for the longest subarray instead of the shortest?
- arrow_right_alt
What if the array contains negative numbers, how would the solution change?
- arrow_right_alt
How would you handle a case where multiple subarrays have the same shortest length but different OR values?