3095.或值至少 K 的最短子数组 I：因为是I所以先暴力枚举（枚举+小优化）

【LetMeFly】3095.或值至少 K 的最短子数组 I：因为是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

解题方法：枚举（小优化）

枚举：

子数组左右端点，计算子数组中元素按位或后的结果，若$\geq k$则更新答案最小值。

小优化：

1. 以l为起点的子数组中：[l, r + 1]子数组的或结果可以由[l, r]子数组的或结果或上一个nums[r + 1]快速得到。
2. 若[l, r]子数组的或结果已经$\geq k$了，则无需再枚举[l, r + 1]等以l为起点的更长的子数组。

• 时间复杂度$O(len(nums)^2)$
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @Author: LetMeFly
 * @Date: 2025-01-16 12:22:16
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-01-16 12:25:45
 */

// 开始读题
class Solution {
public:
    int minimumSubarrayLength(vector<int>& nums, int k) {
        int ans = 100;
        for (int l = 0; l < nums.size(); l++) {
            int val = nums[l];
            for (int r = l; r < nums.size(); r++) {
                val |= nums[r];
                if (val >= k) {
                    ans = min(ans, r - l + 1);
                    break;
                }
            }
        }
        return ans == 100 ? -1 : ans;
    }
};

Python

'''
Author: LetMeFly
Date: 2025-01-16 12:25:24
LastEditors: LetMeFly.xyz
LastEditTime: 2025-01-16 12:27:03
'''
from typing import List

class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        ans = 100
        for l in range(len(nums)):
            val = nums[l]
            for r in range(l, len(nums)):
                val |= nums[r]
                if val >= k:
                    ans = min(ans, r - l + 1)
                    break
        return -1 if ans == 100 else ans

Java

/*
 * @Author: LetMeFly
 * @Date: 2025-01-16 12:27:30
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-01-16 12:29:04
 */
class Solution {
    public int minimumSubarrayLength(int[] nums, int k) {
        int ans = 100;
        for (int l = 0; l < nums.length; l++) {
            int val = nums[l];
            for (int r = l; r < nums.length; r++) {
                val |= nums[r];
                if (val >= k) {
                    ans = Math.min(ans, r - l + 1);
                    break;
                }
            }
        }
        return ans == 100 ? -1 : ans;
    }
}

Go

/*
 * @Author: LetMeFly
 * @Date: 2025-01-16 12:29:34
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-01-16 12:31:29
 */
package main

func minimumSubarrayLength(nums []int, k int) int {
    ans := 100
    for l, val := range nums {
        for r := l; r < len(nums); r++ {
            val |= nums[r]
            if val >= k {
                ans = min(ans, r - l + 1)
                break
            }
        }
    }
    if ans == 100 {
        return -1
    }
    return ans
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/145180094