题目描述
给你一个 非负 整数数组 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 * 1050 <= nums[i] <= 1090 <= k <= 109
解法
方法一：双指针 + 计数
我们可以发现，如果我们固定子数组的左端点，随着右端点向右移动，子数组的按位或值只会增大，不会减小。因此我们可以使用双指针的方法，维护一个满足条件的子数组。
具体地，我们使用两个指针 $i$ 和 $j$ 分别表示子数组的左右端点，初始时两个指针都位于数组的第一个元素。用一个变量 $s$ 表示子数组的按位或值，初始时 $s$ 的值为 $0$。我们还需要维护一个长度为 $32$ 的数组 $cnt$，表示子数组中每个元素的二进制表示中每一位的出现次数。
在每一步操作中，我们将 $j$ 向右移动一位，更新 $s$ 和 $cnt$。如果 $s$ 的值大于等于 $k$，我们不断更新子数组的最小长度，并将 $i$ 向右移动一位，直到 $s$ 的值小于 $k$。在这个过程中，我们也需要更新 $s$ 和 $cnt$。
最后，我们返回最小长度，如果不存在满足条件的子数组，则返回 $-1$。
时间复杂度 $O(n \times \log M)$，空间复杂度 $O(\log M)$，其中 $n$ 和 $M$ 分别是数组的长度和数组中元素的最大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | class Solution:
def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
n = len(nums)
cnt = [0] * 32
ans = n + 1
s = i = 0
for j, x in enumerate(nums):
s |= x
for h in range(32):
if x >> h & 1:
cnt[h] += 1
while s >= k and i <= j:
ans = min(ans, j - i + 1)
y = nums[i]
for h in range(32):
if y >> h & 1:
cnt[h] -= 1
if cnt[h] == 0:
s ^= 1 << h
i += 1
return -1 if ans > n else ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | class Solution {
public int minimumSubarrayLength(int[] nums, int k) {
int n = nums.length;
int[] cnt = new int[32];
int ans = n + 1;
for (int i = 0, j = 0, s = 0; j < n; ++j) {
s |= nums[j];
for (int h = 0; h < 32; ++h) {
if ((nums[j] >> h & 1) == 1) {
++cnt[h];
}
}
for (; s >= k && i <= j; ++i) {
ans = Math.min(ans, j - i + 1);
for (int h = 0; h < 32; ++h) {
if ((nums[i] >> h & 1) == 1) {
if (--cnt[h] == 0) {
s ^= 1 << h;
}
}
}
}
}
return ans > n ? -1 : ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 | class Solution {
public:
int minimumSubarrayLength(vector<int>& nums, int k) {
int n = nums.size();
int cnt[32]{};
int ans = n + 1;
for (int i = 0, j = 0, s = 0; j < n; ++j) {
s |= nums[j];
for (int h = 0; h < 32; ++h) {
if ((nums[j] >> h & 1) == 1) {
++cnt[h];
}
}
for (; s >= k && i <= j; ++i) {
ans = min(ans, j - i + 1);
for (int h = 0; h < 32; ++h) {
if ((nums[i] >> h & 1) == 1) {
if (--cnt[h] == 0) {
s ^= 1 << h;
}
}
}
}
}
return ans > n ? -1 : ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | func minimumSubarrayLength(nums []int, k int) int {
n := len(nums)
cnt := [32]int{}
ans := n + 1
s, i := 0, 0
for j, x := range nums {
s |= x
for h := 0; h < 32; h++ {
if x>>h&1 == 1 {
cnt[h]++
}
}
for ; s >= k && i <= j; i++ {
ans = min(ans, j-i+1)
for h := 0; h < 32; h++ {
if nums[i]>>h&1 == 1 {
cnt[h]--
if cnt[h] == 0 {
s ^= 1 << h
}
}
}
}
}
if ans == n+1 {
return -1
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | function minimumSubarrayLength(nums: number[], k: number): number {
const n = nums.length;
let ans = n + 1;
const cnt: number[] = new Array<number>(32).fill(0);
for (let i = 0, j = 0, s = 0; j < n; ++j) {
s |= nums[j];
for (let h = 0; h < 32; ++h) {
if (((nums[j] >> h) & 1) === 1) {
++cnt[h];
}
}
for (; s >= k && i <= j; ++i) {
ans = Math.min(ans, j - i + 1);
for (let h = 0; h < 32; ++h) {
if (((nums[i] >> h) & 1) === 1 && --cnt[h] === 0) {
s ^= 1 << h;
}
}
}
}
return ans === n + 1 ? -1 : ans;
}
|