LC 3097. 或值至少为 K 的最短子数组 II
题目描述
给你一个 非负 整数数组 nums 和一个整数 k 。
如果一个数组中所有元素的按位或运算 OR 的值 至少 为 k ，那么我们称这个数组是 特别的 。请你返回 nums 中 最短特别非空子数组的长度，如果特别子数组不存在，那么返回 -1 。
- 1 <= nums.length <= 2 * 10^5
- 0 <= nums[i] <= 10^9
- 0 <= k <= 10^9
思考
如果暴力枚举数组的左右端点，时间复杂度O（n^2），就一定会超时，因为n是2e5，所以考虑O（n）或者O（nlogn）的，本题有多种解法。
多个数按位或：如果该位上至少有一个1，那么最后的结果这一位就是1了。
解法1：变长滑动窗口+位运算
本题属于变形的滑动窗口，要当满足条件的时候，左指针移动。
双指针j和i
使用一个哈希表维护j~i中32个位中1的个数
使用val记录区间的按位或的值
时间复杂度O（n）
具体看代码
class Solution:
def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
# 获取数组长度
n = len(nums)
# 创建一个计数器，用于统计每个位上1出现的次数
mp = Counter()
# val变量用于记录当前窗口内所有数字的位或结果
val = 0
# j是滑动窗口的左边界
j = 0
# ans用于记录最短子数组的长度，初始化为正无穷
ans = inf
# 遍历数组nums
for i in range(n):
# 遍历每个数字的31个位（假设整数为32位）
for c in range(31):
# 检查当前位是否为1
if nums[i] >> c & 1:
# 如果为1，则增加对应位的计数
mp[c] += 1
# 如果这是第一个1，则将其代表的数值2^c加到val上
if mp[c] == 1:
val += 1 << c
# 当val大于等于k时，尝试缩小窗口
while j <= i and val >= k:
# 更新最短子数组长度
ans = min(ans, i - j + 1)
# 尝试移动左边界j，并更新val
for c in range(31):
# 如果当前位为1
if nums[j] >> c & 1:
# 减少对应位的计数
mp[c] -= 1
# 如果这是最后一个1，则从val中减去其代表的数值 2^c
if mp[c] == 0:
val -= 1 << c
# 左边界向右移动
j += 1
# 如果找到了符合条件的子数组，返回最短长度；否则返回-1
return ans if ans != inf else -1
如果不熟悉位运算的同学，可以使用数组预处理来模拟
解法二：二分+定长窗口
要求的最短长度有单调性，所以可以用二分答案。check的时候只需要求出某个固定长度区间的最短答案是否满足即可。
相当于check函数是一个定长的滑动窗口，那么每一次就是左右两个数的变化，也可以用方法1的思路解决这个定长的滑动窗口的问题，但其本质是一样的。
时间复杂度O（nlogn）
思考题
如果本题条件换成异或，该怎么做呢?