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

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));// 输出结果

}

在这里插入图片描述