What is the easiest way to start solving Shortest Subarray With OR at Least K I?

Start by checking single elements against k, then expand using a sliding window to track OR and minimize length.

Can brute force work for this problem?

Yes, because nums.length <= 50, checking all subarrays is feasible and helps verify sliding window correctness.

How does bitwise OR affect the sliding window approach?

The OR only increases when adding elements, so contracting the window carefully maintains correctness while minimizing length.

What if no subarray reaches OR >= k?

Return -1, since no special subarray exists according to the problem definition.

Are there edge cases to consider in this sliding window pattern?

Yes, single-element subarrays, zeros in nums, and OR values exactly equal to k require careful handling.

#3095

Easy

auto_awesome滑动窗口（状态滚动更新）

LeetCode 题解工作台

或值至少 K 的最短子数组 I

给你一个非负整数数组 nums 和一个整数 k 。如果一个数组中所有元素的按位或运算 OR 的值至少为 k ，那么我们称这个数组是特别的。请你返回 nums 中最短特别非空子数组的长度，如果特别子数组不存在，那么返回 -1 。示例 1：输入： nums = [1,2,3],…

数组位运算滑动窗口

题目描述

给你一个非负整数数组 nums 和一个整数 k 。

如果一个数组中所有元素的按位或运算 OR 的值至少为 k ，那么我们称这个数组是 特别的 。

请你返回 nums 中 最短特别非空 子数组的长度，如果特别子数组不存在，那么返回 -1 。

示例 1：

输入：nums = [1,2,3], k = 2

输出：1

解释：

子数组 [3] 的按位 OR 值为 3 ，所以我们返回 1 。

注意，[2] 也是一个特别子数组。

示例 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 <= 50
0 <= nums[i] <= 50
0 <= k < 64

lightbulb

解题思路

方法一：双指针 + 计数

我们可以发现，如果我们固定子数组的左端点，随着右端点向右移动，子数组的按位或值只会增大，不会减小。因此我们可以使用双指针的方法，维护一个满足条件的子数组。

具体地，我们使用两个指针 $i$ 和 $j$ 分别表示子数组的左右端点，初始时两个指针都位于数组的第一个元素。用一个变量 $s$ 表示子数组的按位或值，初始时 $s$ 的值为 $0$ 。我们还需要维护一个长度为 $32$ 的数组 $cnt$ ，表示子数组中每个元素的二进制表示中每一位的出现次数。

在每一步操作中，我们将 $j$ 向右移动一位，更新 $s$ 和 $cnt$ 。如果 $s$ 的值大于等于 $k$ ，我们不断更新子数组的最小长度，并将 $i$ 向右移动一位，直到 $s$ 的值小于 $k$ 。在这个过程中，我们也需要更新 $s$ 和 $cnt$ 。

最后，我们返回最小长度，如果不存在满足条件的子数组，则返回 $-1$ 。

时间复杂度 $O(n \times \log M)$ ，空间复杂度 $O(\log M)$ ，其中 $n$ 和 $M$ 分别是数组的长度和数组中元素的最大值。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

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

speed

复杂度分析

指标	值
时间	complexity can range from O(n^2) for brute force to O(n) for sliding window if OR updates are efficient. Space is O(1) if OR is tracked inline, or O(n) if storing prefix OR values.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Consider that small constraints allow simple brute force to verify correctness.
question_mark
The problem favors bit manipulation combined with a sliding window pattern.
question_mark
Expect follow-ups on optimizing OR computations and minimizing window length.

warning

常见陷阱

外企场景

error
Not updating the minimal length after contracting the window.
error
Assuming all subarrays must be longer than 1 instead of checking single elements.
error
Failing to correctly compute OR when elements are added or removed from the window.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the longest subarray with OR less than k.
arrow_right_alt
Return all shortest subarrays with OR at least k.
arrow_right_alt
Modify nums with insertions to guarantee a special subarray exists.

help

常见问题

外企场景

继续练习

#3097 或值至少为 K 的最短子数组 II #3191 使二进制数组全部等于 1 的最少操作次数 I #2935 找出强数对的最大异或值 II