[LeetCode] 每日一题 3095. 或值至少 K 的最短子数组 I

题目链接

https://leetcode.cn/problems/shortest-subarray-with-or-at-least-k-i

题目描述

给你一个 非负 整数数组 nums 和一个整数 k 。

如果一个数组中所有元素的按位或运算 OR 的值 至少 为 k ，那么我们称这个数组是 特别的 。

请你返回 nums 中 最短特别非空 子数组的长度，如果特别子数组不存在，那么返回-1 。

子数组 是数组中连续的 非空 元素序列。

示例输入

示例 1

输入：nums = [1,2,3], k = 2

输出：1

解释：

子数组 [3] 的按位 OR 值为 3 ，所以我们返回 1 。

注意，[2] 也是一个特别子数组。

示例 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 <= 50

• 0 <= nums[i] <= 50

• 0 <= k < 64

解题思路

我们需要找出一个最短的非空子数组，使得这个子数组的按位 OR 运算结果大于等于给定的整数 k。按位 OR 的特性是，如果我们将一个数的 OR 运算与另一个数做合并，结果只会变得更大或相同，永远不会减少。因此，我们可以使用双指针（滑动窗口）的方法来解决这个问题

关键步骤：

1. 按位 OR 操作： 我们可以通过维护一个变量 currentOr 来表示当前子数组的按位 OR 运算结果。随着右端点 j 向右移动，currentOr 会不断增大

2. 双指针： 使用两个指针 i 和 j 分别表示子数组的左右端点。每次右端点 j 向右移动时，我们更新 currentOr。当 currentOr 达到或超过 k 时，我们尝试缩小左端点 i，找出最短的符合条件的子数组。

3. 更新最小长度： 每次 currentOr >= k 时，我们记录当前子数组的长度，并尝试移动左端点来缩小子数组

4. 优化： 使用一个 bitCount 数组来记录子数组中每一位的出现次数。这样我们可以高效地管理按位 OR 的更新

代码实现

class Solution {
    public int minimumSubarrayLength(int[] nums, int k) {
        int n = nums.length;
        // cnt 数组用于记录当前子数组每一位的出现次数
        int[] bitCount = new int[32];
        int minLength = Integer.MAX_VALUE;
        // 双指针方法，i 为子数组的左端点，j 为右端点，s 为当前子数组的按位 OR 值
        for (int i = 0, j = 0, currentOr = 0; j < n; ++j) {
            currentOr |= nums[j];
            for (int bit = 0; bit < 32; ++bit) {
                if ((nums[j] >> bit & 1) == 1) {
                    ++bitCount[bit];
                }
            }
            while (currentOr >= k && i <= j) {
                minLength = Math.min(minLength, j - i + 1);
                // 更新 currentOr 和 bitCount，尝试移除 nums[i]
                for (int bit = 0; bit < 32; ++bit) {
                    if ((nums[i] >> bit & 1) == 1) {
                        if (--bitCount[bit] == 0) {
                            // 如果该位的所有元素都被移除，从 currentOr 中移除该位
                            currentOr ^= 1 << bit;
                        }
                    }
                }
                i++;
            }
        }
        // 如果 minLength 没有被更新过，说明没有找到符合条件的子数组，返回 -1
        return minLength == Integer.MAX_VALUE ? -1 : minLength;
    }
}

复杂度分析

时间复杂度

• 外层循环：右指针 j 每次向右移动一次，最多进行 n 次迭代

• 内层循环：当 currentOr >= k 时，左指针 i 会逐步向右移动。在最坏情况下，左指针 i 可能需要移动至与右指针 j 同样的位置，即最多进行 n 次迭代

• 按位操作：每次更新 bitCount 时，内层循环会遍历最多 32 位，所以按位操作的复杂度是 O(32)，即常数时间

因此，总的时间复杂度是 O(n * 32) = O(n)，其中 n 是数组 nums 的长度

空间复杂度

• 我们使用了一个 bitCount 数组来记录每一位的出现次数，这个数组的大小为 32（因为一个整数最多有 32 位）。所以空间复杂度为 O(32) = O(1)，即常数空间

总结

这道题展示了如何通过双指针和按位 OR 运算结合，利用滑动窗口优化找到最短符合条件的子数组。通过维护按位计数数组，可以高效地管理窗口内的 OR 值，避免了暴力枚举的高时间复杂度。整体思路简洁且高效，适用于许多需要动态更新区间条件的问题

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