或值至少K的最短子数组I

2025-01-16

题目:

给你一个 非负 整数数组 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。我们依次枚举数组中以每个下标 i,并找到以 i 为起始位置的最短特别子数组,并记录最短长度即可,如果数组中不存在特别子数组,则返回 −1。

代码:

class Solution {
public:
    int minimumSubarrayLength(vector<int>& nums, int k) {
        int n = nums.size();
        int res = INT_MAX;
        for (int i = 0; i < n; i++) {
            int value = 0;
            for (int j = i; j < n; j++) {
                value |= nums[j];
                if (value >= k) {
                    res = min(res, j - i + 1);
                    break;
                }
            }
        }
        return res == INT_MAX ? -1 : res;
    }
};