[LeetCode] 每日一题 3097. 或值至少为 K 的最短子数组 II
题目链接
题目描述
给你一个 非负 整数数组 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
解题思路
这道题的核心思想和昨天的题目几乎一致,仍然是采用双指针加定长数组的技巧来解题。具体地,我们使用两个指针 left
和 right
来维护当前的子数组。我们同时维护一个定长数组 bits
,用来记录当前子数组每一位上的 1 的数量。当子数组中按位 OR 的值满足条件时,更新最短子数组的长度。具体步骤如下:
通过右指针扩展子数组,更新
bits
数组当当前子数组满足条件时,尝试通过左指针收缩子数组,更新最短子数组长度
重复上述过程,直到右指针遍历完整个数组
最终返回最短子数组的长度,如果不存在符合条件的子数组,则返回 -1
代码实现
class Solution {
public int minimumSubarrayLength(int[] nums, int k) {
int ans = Integer.MAX_VALUE;
int[] bits = new int[30];
int left = 0, right = 0;
while (right < nums.length) {
for (int i = 0; i < 30; i++) {
bits[i] += (nums[right] >> i) & 1;
}
// 检查当前子数组是否满足条件
while (left <= right && check(bits, k)) {
ans = Math.min(ans, right - left + 1);
// 缩小左指针,更新按位 OR 的值
for (int i = 0; i < 30; i++) {
bits[i] -= (nums[left] >> i) & 1;
}
left++;
}
right++;
}
// 如果没有找到符合条件的子数组,返回 -1
return ans == Integer.MAX_VALUE ? -1 : ans;
}
private boolean check(int[] bits, int k) {
int num = 0;
for (int i = 0; i < bits.length; i++) {
if (bits[i] > 0) {
num |= 1 << i;
}
if (num >= k) {
return true;
}
}
return false;
}
}
复杂度分析
时间复杂度:
O(n * 30)
,其中n
是数组nums
的长度。每次扩展右指针时,我们需要遍历bits
数组的每一位(共 30 位),同时每次收缩左指针时也需要遍历bits
数组。因此,时间复杂度为O(n * 30)
,简化后为O(n)
空间复杂度:
O(30)
,bits
数组的大小是固定的,为 30。因此,空间复杂度为O(30)
,简化后为O(1)
总结
这道题与昨天的题目相似,依然使用双指针和定长数组的技巧,通过维护当前子数组的按位 OR 值,快速判断是否满足条件。时间复杂度较为优秀,适用于大规模数据。通过这种方法,能够在不断调整子数组范围的同时,找到最短符合条件的子数组
希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。