目标
给你一个 非负 整数数组 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
思路
求数组 nums 的最短特别子数组长度，特别子数组的所有元素按位与的结果大于等于 k。
枚举子数组，暴力求解每个子数组的或值。
代码
/**
* @date 2025-01-16 22:22
*/
public class MinimumSubarrayLength3095 {
/**
* 枚举起点 O(n^2)
*/
public int minimumSubarrayLength_v1(int[] nums, int k) {
int n = nums.length;
int res = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
int or = 0;
for (int j = i; j < n; j++) {
or |= nums[j];
if (or >= k) {
res = Math.min(res, j - i + 1);
break;
}
}
}
return res == Integer.MAX_VALUE ? -1 : res;
}
/**
* 枚举终点 O(n^3)
*/
public int minimumSubarrayLength(int[] nums, int k) {
int n = nums.length;
int res = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
int or = 0;
for (int x = j; x <= i; x++) {
or |= nums[x];
}
if (or >= k) {
res = Math.min(res, i - j + 1);
}
}
}
return res == Integer.MAX_VALUE ? -1 : res;
}
}
性能
