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

难度：简单

题目

给你一个 非负 整数数组 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

Reference

题解

以下所指“条件”是指区间按位或的值大于等于k。

注意到x | y >= x以及x | y >= y，因此：

• 若一个区间[l:r]满足条件，则以l开头的所有后续区间都满足条件。
• 若一个区间[l:r]不满足条件，则以r结尾的所有之前的区间都不满足条件。

可以用滑动窗口的思路，设置一个区间[l:r]并记录区间内数值的按位或的值。首先向右延伸区间（递增r），找到一个满足条件的区间后：

• 从右向左寻找最短的满足条件的区间，作为当前找到的最短区间
• 将l的值设为最长的不满足条件区间的起点

之后继续向右移动r，寻找下一个满足条件的区间。

class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        min_range, right_or_value = len(nums) + 1, 0
        for r, value in enumerate(nums):
            right_or_value |= value

            if right_or_value >= k:
                l, left_or_value, right_or_value = r - 1, value, 0
                while l >= 0 and left_or_value < k:
                    left_or_value |= nums[l]
                    right_or_value |= nums[l + 1]
                    l -= 1
                min_range = min(min_range, r - l)
        return -1 if min_range > len(nums) else min_range

评论