2024-11-09：或值至少为 K 的最短子数组 II。用go语言，给定一个非负整数数组 nums 和一个整数 k，我们的目标

福大大架构师每日一题

发布于 2024-11-11 19:53:52

15000

代码可运行

运行总次数：0

代码可运行

2024-11-09：或值至少为 K 的最短子数组 II。用go语言，给定一个非负整数数组 nums 和一个整数 k，我们的目标是找出数组中最短的非空子数组，使得该子数组所有元素的按位或结果至少为 k。如果找不到这样的子数组，则返回 -1。

具体要求是：查找满足条件的最短子数组长度，如果不存在这样的子数组，返回 -1。

输入：nums = [2,1,8], k = 10。

输出：3。

解释：

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

答案2024-11-09：

chatgpt

题目来自leetcode3097。

大体步骤如下：

1.初始化变量:

• 使用 ans 来保存当前找到的最短子数组的长度。初始值设为 math.MaxInt，表示一个很大的数。
• 定义一个结构体 pair，用于保存当前子数组的 OR 值和左端点。
• 创建一个空的切片 ors 来存储每个右端点的状态。

2.遍历数组:

• 使用 for 循环遍历 nums 数组的每个元素，其中 i 是当前元素的索引，x 是该元素的值。
• 对于每个新元素 x，在 ors 切片末尾追加一个初始值 (0, i)，表示当前 OR 值为 0，左端点为当前索引 i。

3.更新 OR 值:

• 使用一个索引 j 来管理 ors 切片，初始化为 0。
• 内部的 for 循环遍历 ors 中的每一个元素，更新其 OR 值：
- • 计算 p.or |= x，将当前元素 x 赋值给对应的 pair 中的 or。
- • 如果当前 OR 值 p.or 大于等于 k，计算子数组长度 i - p.left + 1，并可能更新 ans。

4.处理去重和索引管理:

• 检查当前 OR 值与第 j 个 ors 中的 OR 值是否相同。如果相同，更新 ors[j].left 为当前子数组的左端点，表示合并。
• 如果不同，更新 j 并将当前的 pair 复制到 ors[j] 中，新的 j 值便表示下一个空位。
• 最后，通过 ors.truncate(j + 1) 的方式将多余的元素通过切片管理去除。

5.返回结果:

• 在遍历结束后，检查 ans 是否依然是 math.MaxInt，如果是，则返回 -1 表示没有找到满足条件的子数组。
• 否则返回找到的最短子数组的长度 ans。

时间复杂度分析

• 主要的时间消耗来自于外层的遍历 nums，这是 O(n)。内部的 for 循环在某些情况下也可能遍历 ors 切片。最坏情况下，ors 的大小可以接近 n，因此最坏情况下的复杂度是 O(n^2)，但在实际中，由于去重和 OR 操作，平均情况下通常会好很多。

空间复杂度分析

• 空间方面，ors 最多会存储与 nums 长度相等的元素。所以空间复杂度是 O(n)。此外，除了原始输入数组外，所用的额外空间主要集中在 ors 切片上。

总结

• 总时间复杂度: O(n^2)（最坏情况）；平均情况会更好。
• 总额外空间复杂度: O(n)。

Go完整代码如下：

package main

import(
"fmt"
"math"
)

func minimumSubarrayLength(nums []int, k int)int{
    ans := math.MaxInt
type pair struct{or, left int}
    ors :=[]pair{}// 保存 (右端点为 i 的子数组 OR, 该子数组左端点的最大值)
for i, x :=range nums {
        ors =append(ors, pair{0, i})
        j :=0
for idx :=range ors {
            p :=&ors[idx]
            p.or|= x
if p.or>= k {
                ans = min(ans, i-p.left+1)
}
if ors[j].or== p.or{
                ors[j].left = p.left // 原地去重：合并相同值，左端点取靠右的
}else{
                j++
                ors[j]=*p
}
}
        ors = ors[:j+1]// 去重：移除多余元素
}
if ans == math.MaxInt{
return-1
}
return ans
}

func main(){
    nums :=[]int{2,1,8}
    k :=10
    fmt.Println(minimumSubarrayLength(nums, k))
}

Rust完整代码如下：

use std::cmp;

fnminimum_subarray_length(nums:&[i32], k:i32)->i32{
letmut ans= i32::MAX;
letmut ors:Vec<(i32,usize)>=Vec::new();// 保存 (当前 OR 值, 左端点索引)

for(i,&x)in nums.iter().enumerate(){
// 向 ors 添加一个新元素
        ors.push((0, i));
letmut j=0;

foridxin0..ors.len(){
let(or_val, left)= ors[idx];

// 更新当前的 OR 值
letnew_or= or_val | x;

// 检查是否满足条件
if new_or >= k {
                ans = cmp::min(ans,(i - left +1)asi32);
}

// 原地去重逻辑
if j >0&& ors[j -1].0== new_or {
                ors[j -1].1= left;// 更新左端点为靠右的值
}else{
// 存储新的 OR 值
if j < ors.len(){
                    ors[j]=(new_or, left);
}else{
                    ors.push((new_or, left));
}
                j +=1;
}
}

// 去重：保留有效元素
        ors.truncate(j);
}

if ans == i32::MAX {
-1// 如果没有找到合适的子数组
}else{
        ans // 返回找到的最短子数组长度
}
}

fnmain(){
letnums=vec![2,1,8];
letk=10;
println!("{}",minimum_subarray_length(&nums, k));// 输出结果
}