Medium

题目描述

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

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

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

示例 1：

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

示例 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 <= 2 * 10^5
  • 0 <= nums[i] <= 10^9
  • 0 <= k <= 10^9

解题思路

解题思路

这道题需要找到按位或值至少为 k 的最短子数组。关键观察是按位或运算的性质：只会设置新的位，永远不会取消已设置的位。

核心思想

  1. 状态维护：对于每个位置 i，我们需要维护所有以 i 结尾的子数组的按位或值。
  2. 去重优化：由于按位或的单调性，以某个位置结尾的所有子数组的按位或值最多只有 32 种不同的值（对应 32 个二进制位）。
  3. 状态转移：从位置 i-1 的状态转移到位置 i 时，将 nums[i] 与所有之前的或值进行或运算。

算法流程

  1. 维护一个集合，存储 (或值, 对应的最短长度) 对
  2. 对于每个元素 nums[i]：
    • 将 nums[i] 本身作为长度为 1 的子数组加入
    • 对之前的所有或值与 nums[i] 进行或运算，更新状态
    • 去除重复的或值，只保留最短长度
    • 检查是否有或值 ≥ k，更新答案

这种方法利用了按位或的单调性，将时间复杂度优化到了 O(n log max(nums))。

代码实现

class Solution {
public:
    int minimumSubarrayLength(vector<int>& nums, int k) {
        if (k == 0) return 1;
        
        int n = nums.size();
        int result = INT_MAX;
        
        // 存储 (or_value, min_length) 对
        vector<pair<int, int>> prev;
        
        for (int i = 0; i < n; i++) {
            vector<pair<int, int>> curr;
            
            // 添加当前元素作为单独的子数组
            curr.push_back({nums[i], 1});
            
            // 扩展之前的子数组
            for (auto& p : prev) {
                int newOr = p.first | nums[i];
                curr.push_back({newOr, p.second + 1});
            }
            
            // 去重，保留最短长度
            prev.clear();
            for (auto& p : curr) {
                if (p.first >= k) {
                    result = min(result, p.second);
                }
                
                // 只保留不重复的or值，且保留最短长度
                bool found = false;
                for (auto& existing : prev) {
                    if (existing.first == p.first) {
                        existing.second = min(existing.second, p.second);
                        found = true;
                        break;
                    }
                }
                if (!found) {
                    prev.push_back(p);
                }
            }
        }
        
        return result == INT_MAX ? -1 : result;
    }
};

class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        if k == 0:
            return 1
        
        result = float('inf')
        prev = []  # 存储 (or_value, min_length) 对
        
        for num in nums:
            curr = [(num, 1)]  # 当前元素作为单独子数组
            
            # 扩展之前的子数组
            for or_val, length in prev:
                new_or = or_val | num
                curr.append((new_or, length + 1))
            
            # 去重，保留最短长度
            prev = []
            seen = {}
            
            for or_val, length in curr:
                if or_val >= k:
                    result = min(result, length)
                
                if or_val not in seen:
                    seen[or_val] = length
                else:
                    seen[or_val] = min(seen[or_val], length)
            
            prev = list(seen.items())
        
        return result if result != float('inf') else -1

public class Solution {
    public int MinimumSubarrayLength(int[] nums, int k) {
        if (k == 0) return 1;
        
        int result = int.MaxValue;
        var prev = new List<(int orValue, int length)>();
        
        foreach (int num in nums) {
            var curr = new List<(int, int)> { (num, 1) };
            
            // 扩展之前的子数组
            foreach (var (orValue, length) in prev) {
                int newOr = orValue | num;
                curr.Add((newOr, length + 1));
            }
            
            // 去重，保留最短长度
            prev.Clear();
            var seen = new Dictionary<int, int>();
            
            foreach (var (orValue, length) in curr) {
                if (orValue >= k) {
                    result = Math.Min(result, length);
                }
                
                if (!seen.ContainsKey(orValue)) {
                    seen[orValue] = length;
                } else {
                    seen[orValue] = Math.Min(seen[orValue], length);
                }
            }
            
            foreach (var kvp in seen) {
                prev.Add((kvp.Key, kvp.Value));
            }
        }
        
        return result == int.MaxValue ? -1 : result;
    }
}

var minimumSubarrayLength = function(nums, k) {
    if (k === 0) return 1;
    
    let n = nums.length;
    let minLength = Infinity;
    
    for (let i = 0; i < n; i++) {
        let or = 0;
        for (let j = i; j < n; j++) {
            or |= nums[j];
            if (or >= k) {
                minLength = Math.min(minLength, j - i + 1);
                break;
            }
        }
    }
    
    return minLength === Infinity ? -1 : minLength;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度分析
时间复杂度O(n × log(max(nums)))，其中 n 是数组长度。由于按位或的单调性，每个位置最多维护 32 种不同的或值
空间复杂度O(log(max(nums)))，存储不同或值和对应长度的空间

相关题目