2024-10-30：或值至少 K 的最短子数组 I。用go语言，给定一个非负整数数组 nums 和一个整数 k，我们需要判断数

2024-10-30：或值至少 K 的最短子数组 I。用go语言，给定一个非负整数数组 nums 和一个整数 k，我们需要判断数组中是否存在一个最短的非空子数组，使得该子数组所有元素的按位或（OR）运算结果至少为 k。如果找到了这样的子数组，返回其长度；如果不存在，则返回 -1。

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

输出：1。

解释：

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

注意，[2] 也是一个特别子数组。

答案2024-10-30：

chatgpt

题目来自leetcode3095。

大体步骤如下：

代码逻辑分析

1.初始化：

•minLen被设置为math.MaxInt32，用于存储找到的最短子数组的长度。

•n是数组nums的长度。

2.解决方案 1：

• 对于每一个索引i从0到n-1，表示当前子数组的结束位置。

• 对于每一个j从i递减到0，表示当前子数组的起始位置。

• 检查从j到i这段子数组的按位或结果，调用isSpecial函数。

• 如果返回的结果满足大于等于k，则更新minLen为当前子数组长度i-j+1的最小值。

• 最后，如果没有找到满足条件的子数组，返回-1；否则返回minLen。

3.isSpecial 函数：

• 接受数组nums和子数组的起始、结束索引j、i，以及目标值k。

• 初始化结果res为0。

• 遍历子数组，计算位或结果res |= nums[idx]。

• 最后返回一个布尔值，判断res是否大于等于k。

4.解决方案 2：

• 该方法做了优化，先检查当前元素nums[i]是否已经大于等于k，如果是，则直接返回1，因为单独的元素就满足了条件。

• 同样遍历j，更新nums[j]为nums[j] | nums[i]。并检查是否满足按位或条件。

• 如果找到了满足条件的子数组，则更新minLen。

• 最后根据minLen的最终值返回结果。

时间复杂度

•解决方案 1：最坏情况下，外层循环和内层循环都是进行O(n^2)的遍历。

•解决方案 2：外层循环为O(n)，内层循环的最坏情况下为O(n)，因此在某些情况下也可能达到O(n^2)的复杂度。

•最终时间复杂度：最坏情况为O(n^2)。

空间复杂度

• 两种解决方案都只使用了常量级的额外空间，主要是用于存储变量minLen和中间结果res，以及输入数组nums本身。没有使用额外的数据结构来增加空间开销。

•最终空间复杂度：O(1)。

总结

代码通过两种方式实现了目标，虽然最坏情况下时间复杂度达到O(n^2)但在实际操作中，尤其是对于较小的输入数组，可能表现良好。空间复杂度保持在常数级别，确保了算法的高效性。

Go完整代码如下：

package main

import(

"fmt"

"math"

)

func minimumSubarrayLength(nums []int, k int)int{

minLen := math.MaxInt32

n :=len(nums)

// 解决方案 1 的实现

for i :=0; i < n; i++{

for j := i; j >=0; j--{

if isSpecial(nums, j, i, k){

minLen = min(minLen, i-j+1)

}

}

}

if minLen == math.MaxInt32{

return-1

}

return minLen

}

func isSpecial(nums []int, j int, i int, k int)bool{

res :=0

for idx := j; idx <= i; idx++{

res |= nums[idx]

}

return res >= k

}

func min(a, b int)int{

if a < b {

return a

}

return b

}

// 解决方案 2 的实现

func minimumSubarrayLengthOptimized(nums []int, k int)int{

minLen := math.MaxInt32

n :=len(nums)

for i :=0; i < n; i++{

if nums[i]>= k {

return1

}

for j := i -1; j >=0&&(nums[i]|nums[j])!= nums[j]; j--{

nums[j]|= nums[i]

if nums[j]>= k {

minLen = min(minLen, i-j+1)

}

}

}

if minLen == math.MaxInt32{

return-1

}

return minLen

}

func main(){

nums :=[]int{1,2,3}

k :=2

fmt.Println(minimumSubarrayLength(nums, k))

fmt.Println(minimumSubarrayLengthOptimized(nums, k))

}

在这里插入图片描述Rust完整代码如下：

use std::cmp;

fnminimum_subarray_length(nums:Vec<i32>, k:i32)->i32{

letmut min_len= i32::MAX;

letn= nums.len();

// 解决方案 1 的实现

foriin0..n {

forjin(0..=i).rev(){

ifis_special(&nums, j, i, k){

min_len = cmp::min(min_len,(i - j +1)asi32);

}

}

}

if min_len == i32::MAX {

-1

}else{

min_len

}

}

fnis_special(nums:&Vec<i32>, j:usize, i:usize, k:i32)->bool{

letmut res=0;

foridxin j..=i {

res |= nums[idx];

}

res >= k

}

fnminimum_subarray_length_optimized(nums:Vec<i32>, k:i32)->i32{

letmut min_len= i32::MAX;

letmut nums= nums.clone();// 复制一份 nums

letn= nums.len();

foriin0..n {

if nums[i]>= k {

return1;

}

forjin(0..i).rev(){

if(nums[i]| nums[j])!= nums[j]{

nums[j]|= nums[i];

if nums[j]>= k {

min_len = cmp::min(min_len,(i - j +1)asi32);

}

}else{

break;// 提高效率，如果不再变化，则可直接跳出

}

}

}

if min_len == i32::MAX {

-1

}else{

min_len

}

}

fnmain(){

letnums=vec![1,2,3];

letk=2;

println!("{}",minimum_subarray_length(nums.clone(), k));// 解决方案 1

println!("{}",minimum_subarray_length_optimized(nums, k));// 解决方案 2

}

在这里插入图片描述