题目描述
给你一个 非负 整数数组 nums
和一个整数 k
。
如果一个数组中所有元素的按位或运算 OR
的值 至少 为 k
,那么我们称这个数组是 特别的。
请你返回 nums
中 最短特别非空 子数组的长度,如果特别子数组不存在,那么返回 -1
。
样例
输入:nums = [1,2,3], k = 2
输出:1
解释:
子数组 [3] 的按位 OR 值为 3,所以我们返回 1。
输入:nums = [2,1,8], k = 10
输出:3
解释:
子数组 [2,1,8] 的按位 OR 值为 11,所以我们返回 3。
输入:nums = [1,2], k = 0
输出:1
解释:
子数组 [1] 的按位 OR 值为 1,所以我们返回 1。
限制
1 <= nums.length <= 50
0 <= nums[i] <= 50
0 <= k < 64
算法
(暴力枚举) $O(n^2)$
- 枚举子数组的起点,然后暴力枚举子数组的终点,如果中途发现
OR
值大于 $k$,则终止枚举终点并更新答案。
时间复杂度
- 最坏情况下,两层循环暴力枚举的时间复杂度为 $O(n^2)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int minimumSubarrayLength(vector<int>& nums, int k) {
const int n = nums.size();
int ans = INT_MAX;
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = i; j < n; j++) {
sum |= nums[j];
if (sum >= k) {
ans = min(ans, j - i + 1);
break;
}
}
}
if (ans == INT_MAX)
ans = -1;
return ans;
}
};