题目描述
给你一个 非负 整数数组 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 <= 2 * 10^5
0 <= nums[i] <= 10^9
0 <= k <= 10^9
算法
(滑动窗口) $O(n \log k)$
- 对于每个区间右端点 $r$,找到尽可能大的区间左端点 $l$,满足区间 $[l, r]$ 的
OR
值大于等于 $k$。 - 维护一个变量 $sum$,代表当前区间的
OR
值,以及一个长度为 $\log k$ 的数组 $cnt$,表示每一位的出现次数。 - 移动 $r$ 时,分别更新 $sum$ 和 $cnt$ 的值。如果 $sum \ge k$,则更新答案并不断地移动 $l$,直到不再满足条件。
时间复杂度
- 每个位置遍历两次,每次移动 $r$ 或 $l$,操作 $cnt$ 的时间复杂度为 $O(\log k)$,故总时间复杂度为 $O(n \log k)$。
空间复杂度
- 需要 $O(\log k)$ 的额外空间存储 $cnt$。
C++ 代码
class Solution {
private:
void add(int x, vector<int> &cnt, int &sum) {
sum |= x;
for (int i = 0; i < 31; i++)
if ((x >> i) & 1)
++cnt[i];
}
void remove(int x, vector<int> &cnt, int &sum) {
for (int i = 0; i < 31; i++) {
if (!((x >> i) & 1))
continue;
--cnt[i];
if (cnt[i] == 0)
sum ^= 1 << i;
}
}
public:
int minimumSubarrayLength(vector<int>& nums, int k) {
const int n = nums.size();
vector<int> cnt(31, 0);
int sum = 0;
int ans = INT_MAX;
for (int l = 0, r = 0; r < n; r++) {
add(nums[r], cnt, sum);
while (l <= r && sum >= k) {
ans = min(ans, r - l + 1);
remove(nums[l], cnt, sum);
l++;
}
}
if (ans == INT_MAX)
ans = -1;
return ans;
}
};