Leetcode3097：或值至少为 K 的最短子数组 II

题目描述：

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

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

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

代码思路：

1. 初始化变量：
   • length：数组 nums 的长度。
   • MIN：用于记录最短子数组的长度，初始值设为 length + 1（一个不可能达到的长度，用于后续判断是否存在符合条件的子数组）。
   • l、r：分别表示当前考虑的子数组的左右边界（左闭右闭）。
   • ans：用于存储当前右边界 r 及其左侧所有元素的按位或结果。
2. 遍历数组：
   • 使用 while 循环遍历数组，r 表示当前考察的右边界。
   • 在每次循环中，更新 ans 为从 l 到 r 的所有元素的按位或结果。
   • 如果 ans >= k，则尝试从右向左找到一个最短的子数组，使得其按位或结果不小于 k。
3. 内部循环：
   • 从 r 到 l-1 向左遍历，尝试找到一个最短的满足条件的子数组。
   • 使用 temp 和 pre 变量来记录当前和上一个位置的按位或结果。
   • 如果找到一个满足条件的子数组，更新 MIN、l 和 ans。
4. 结果判断：
   • 如果 MIN 仍然是 length + 1，说明没有找到符合条件的子数组，返回 -1。
   • 否则，返回 MIN。

代码实现：

class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        length = len(nums)
        MIN = length + 1
        l = r = ans = 0
        while(r < length):
            ans = ans | nums[r]
            if ans >= k:
                temp = pre = 0
                for i in range(r, l-1, -1):
                    pre = temp
                    temp = temp | nums[i]
                    if temp >= k:
                        MIN = min(MIN, r-i+1)
                        l = i + 1
                        ans = pre
                        break
            r += 1
        if MIN == length + 1:
            return -1
        return MIN

 

 

原文地址：https://blog.csdn.net/m0_67598823/article/details/145214941

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！