3097. 或值至少为 K 的最短子数组 II

🟠   🔖  位运算 数组 滑动窗口  🔗 力扣 LeetCode

题目

You are given an array nums of non-negative integers and an integer k.

An array is called special if the bitwise OR of all of its elements is at least k.

Return the length of theshortest special non-empty subarray ofnums, or return -1 if no special subarray exists.

Example 1:

Input: nums = [1,2,3], k = 2

Output: 1

Explanation:

The subarray [3] has OR value of 3. Hence, we return 1.

Example 2:

Input: nums = [2,1,8], k = 10

Output: 3

Explanation:

The subarray [2,1,8] has OR value of 11. Hence, we return 3.

Example 3:

Input: nums = [1,2], k = 0

Output: 1

Explanation:

The subarray [1] has OR value of 1. Hence, we return 1.

Constraints:

• 1 <= nums.length <= 2 * 10^5
• 0 <= nums[i] <= 10^9
• 0 <= k <= 10^9

题目大意

给你一个 非负 整数数组 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

解题思路

可以使用滑动窗口和位计数数组来有效计算窗口中所有数的按位 OR 值。

1. 滑动窗口：用两个指针 start 和 end 形成一个窗口 [start, end]。end 向右扩展窗口，start 向右收缩窗口。

2. 位计数数组 count：

   • count[i] 表示当前窗口中有多少个数在二进制的第 i 位上是 1。
   • 使用 updateBits 函数来更新 count 数组。对窗口右边界 nums[end] 调用 updateBits 使窗口扩展，对窗口左边界 nums[start] 调用 updateBits 使窗口收缩。

3. 快速计算 OR 值：

   • 在 getVal 函数中，将 count 数组转化为 OR 值。只要 count[i] > 0，就说明该位上至少有一个 1，在 OR 运算中该位也应为 1。
   • 当 getVal(count) >= k 时，窗口满足条件，更新 minLength。

4. 更新最小长度：

   • 当窗口的 OR 值满足 >= k 时，计算当前窗口的长度并更新最小长度 minLength。
   • 然后右移 start 收缩窗口，直到不再满足 getVal(count) >= k 为止。

复杂度分析

• 时间复杂度：O(n)，需要遍历 n 个元素，每次更新窗口的位计数数组需要 O(32) 操作。
• 空间复杂度：O(1)，用于存储位计数数组 count 占用O(32)的空间，也就是O(1)。

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
function minimumSubarrayLength(nums, k) {
	const count = Array(32).fill(0); // 位计数数组
	let start = 0,
		minLength = nums.length + 1;

	for (let end = 0; end < nums.length; end++) {
		// 更新窗口的 OR 结果
		updateBits(count, nums[end], 1);

		// 符合条件的情况下，尝试缩小窗口
		while (start <= end && getVal(count) >= k) {
			minLength = Math.min(minLength, end - start + 1);
			updateBits(count, nums[start], -1);
			start++;
		}
	}
	return minLength === nums.length + 1 ? -1 : minLength;
}

// 更新位计数数组
function updateBits(count, num, val) {
	for (let i = 0; i < 32; i++) {
		if ((num & (1 << i)) !== 0) {
			count[i] += val;
		}
	}
}

// 根据位计数数组生成当前窗口的 OR 值
function getVal(count) {
	let ans = 0;
	for (let i = 0; i < 32; i++) {
		if (count[i] > 0) {
			ans |= 1 << i;
		}
	}
	return ans;
}

相关题目

题号	标题	题解	标签	难度	力扣
325	和等于 k 的最长子数组长度 🔒		数组 哈希表 前缀和	🟠	🀄️ 🔗
862	和至少为 K 的最短子数组	[✓]	队列 数组 二分查找 4+	🔴	🀄️ 🔗