文章

[LeetCode] 每日一题 3097. 或值至少为 K 的最短子数组 II

题目链接

https://leetcode.cn/problems/shortest-subarray-with-or-at-least-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

解题思路

这道题的核心思想和昨天的题目几乎一致,仍然是采用双指针加定长数组的技巧来解题。具体地,我们使用两个指针 leftright 来维护当前的子数组。我们同时维护一个定长数组 bits,用来记录当前子数组每一位上的 1 的数量。当子数组中按位 OR 的值满足条件时,更新最短子数组的长度。具体步骤如下:

  1. 通过右指针扩展子数组,更新 bits 数组

  2. 当当前子数组满足条件时,尝试通过左指针收缩子数组,更新最短子数组长度

  3. 重复上述过程,直到右指针遍历完整个数组

  4. 最终返回最短子数组的长度,如果不存在符合条件的子数组,则返回 -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 值,快速判断是否满足条件。时间复杂度较为优秀,适用于大规模数据。通过这种方法,能够在不断调整子数组范围的同时,找到最短符合条件的子数组

希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。

License:  CC BY 4.0