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

标题描述：

给你一个 非负 整数数组 nums 和一个整数 k 。
假如一个数组中全部元素的按位或运算 OR 的值 至少 为 k ，那么我们称这个数组是 特别的 。
请你返回 nums 中 最短特别非空 子数组的长度，假如特别子数组不存在，那么返回 -1 。
代码思绪：

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

代码实现：

1. class Solution:
2.     def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
3.         length = len(nums)
4.         MIN = length + 1
5.         l = r = ans = 0
6.         while(r < length):
7.             ans = ans | nums[r]
8.             if ans >= k:
9.                 temp = pre = 0
10.                 for i in range(r, l-1, -1):
11.                     pre = temp
12.                     temp = temp | nums[i]
13.                     if temp >= k:
14.                         MIN = min(MIN, r-i+1)
15.                         l = i + 1
16.                         ans = pre
17.                         break
18.             r += 1
19.         if MIN == length + 1:
20.             return -1
21.         return MIN

复制代码

 
 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。