Easy

题目描述

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

如果一个数组的所有元素按位或运算的结果至少为 k，则称这个数组是 特殊的。

返回 nums 中最短的特殊非空子数组的长度，如果不存在特殊子数组，则返回 -1。

示例 1：

输入：nums = [1,2,3], k = 2
输出：1
解释：子数组 [3] 的或运算值为 3。因此，我们返回 1。
注意 [2] 也是一个特殊子数组。

示例 2：

输入：nums = [2,1,8], k = 10
输出：3
解释：子数组 [2,1,8] 的或运算值为 11。因此，我们返回 3。

示例 3：

输入：nums = [1,2], k = 0
输出：1
解释：子数组 [1] 的或运算值为 1。因此，我们返回 1。

约束条件：

  • 1 <= nums.length <= 50
  • 0 <= nums[i] <= 50
  • 0 <= k < 64

解题思路

这是一道位运算和子数组的经典问题。由于数据规模较小（n ≤ 50），我们可以采用暴力枚举的方法。

解题思路：

  1. 暴力枚举所有子数组：由于约束条件较小，我们可以枚举所有可能的子数组，计算每个子数组的按位或值。

  2. 按位或运算的性质：

    • 按位或运算具有单调性：a | b >= max(a, b)
    • 随着子数组长度增加，按位或值只会增大或保持不变，不会减小

  3. 优化策略：

    • 从长度为1开始枚举子数组长度
    • 对于每个长度，检查所有该长度的子数组
    • 一旦找到满足条件的子数组就立即返回，因为我们要找最短的

  4. 实现细节：

    • 外层循环控制子数组长度（从1到n）
    • 内层循环控制起始位置
    • 计算当前子数组的按位或值
    • 如果按位或值 >= k，返回当前长度

推荐解法：暴力枚举（在当前约束下最直接有效）

代码实现

class Solution {
public:
    int minimumSubarrayLength(vector<int>& nums, int k) {
        int n = nums.size();
        
        // 枚举子数组长度
        for (int len = 1; len <= n; len++) {
            // 枚举起始位置
            for (int i = 0; i <= n - len; i++) {
                int orValue = 0;
                // 计算当前子数组的按位或值
                for (int j = i; j < i + len; j++) {
                    orValue |= nums[j];
                }
                // 如果满足条件，返回当前长度
                if (orValue >= k) {
                    return len;
                }
            }
        }
        
        return -1;
    }
};

class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        n = len(nums)
        
        # 枚举子数组长度
        for length in range(1, n + 1):
            # 枚举起始位置
            for i in range(n - length + 1):
                or_value = 0
                # 计算当前子数组的按位或值
                for j in range(i, i + length):
                    or_value |= nums[j]
                # 如果满足条件，返回当前长度
                if or_value >= k:
                    return length
        
        return -1

public class Solution {
    public int MinimumSubarrayLength(int[] nums, int k) {
        int n = nums.Length;
        
        // 枚举子数组长度
        for (int len = 1; len <= n; len++) {
            // 枚举起始位置
            for (int i = 0; i <= n - len; i++) {
                int orValue = 0;
                // 计算当前子数组的按位或值
                for (int j = i; j < i + len; j++) {
                    orValue |= nums[j];
                }
                // 如果满足条件，返回当前长度
                if (orValue >= k) {
                    return len;
                }
            }
        }
        
        return -1;
    }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minimumSubarrayLength = function(nums, k) {
    const n = nums.length;
    
    // 枚举子数组长度
    for (let len = 1; len <= n; len++) {
        // 枚举起始位置
        for (let i = 0; i <= n - len; i++) {
            let orValue = 0;
            // 计算当前子数组的按位或值
            for (let j = i; j < i + len; j++) {
                orValue |= nums[j];
            }
            // 如果满足条件，返回当前长度
            if (orValue >= k) {
                return len;
            }
        }
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n³)三层嵌套循环：长度枚举O(n)，起始位置枚举O(n)，计算按位或O(n)
空间复杂度O(1)只使用常数额外空间

相关题目