目标
给你一个 非负 整数数组 nums 和一个整数 k 。
如果一个数组中所有元素的按位或运算 OR 的值 至少 为 k ，那么我们称这个数组是 特别的 。
请你返回 nums 中 最短特别非空 子数组 的长度，如果特别子数组不存在，那么返回 -1 。
示例 1：
输入：nums = [1,2,3], k = 2
输出：1
解释：
子数组 [3] 的按位 OR 值为 3 ，所以我们返回 1 。示例 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 <= 2 * 10^5
- 0 <= nums[i] <= 10^9
- 0 <= k <= 10^9
思路
求数组 nums 的最短特别子数组长度，特别子数组的所有元素按位与的结果大于等于 k。
与 3095.或值至少K的最短子数组I 相比数据范围变大了，O(n^2) 的解法会超时。
记录每一位的出现次数，使用滑动窗口，枚举右收缩左。由于 按位或 没有逆运算，我们可以反向重新计算 按位与。
代码
/**
* @date 2025-01-17 8:40
*/
public class MinimumSubarrayLength3097 {
public int minimumSubarrayLength_v2(int[] nums, int k) {
int res = Integer.MAX_VALUE;
int right = 0;
int n = nums.length;
int or = 0;
while (right < n) {
do {
or |= nums[right++];
} while (right < n && or < k);
if (or >= k) {
int left = right - 1;
int tmp = 0;
while (left >= 0) {
tmp |= nums[left--];
if (tmp >= k) {
left++;
break;
} else {
or = tmp;
}
}
res = Math.min(res, right - left);
} else {
break;
}
}
return res == Integer.MAX_VALUE ? -1 : res;
}
}
性能
