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 mainimport("fmt""math")func minimumSubarrayLength(nums []int, k int)int{ ans := math.MaxInttype pair struct{or, left int} ors :=[]pair{}// 保存 (右端点为 i 的子数组 OR, 该子数组左端点的最大值)for i, x :=range nums { ors =append(ors, pair{0, i}) j :=0for idx :=range ors { p :=&ors[idx] p.or|= xif 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));// 输出结果}

在这里插入图片描述