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：
题目来自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 {
return 1
}
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;
fn minimum_subarray_length(nums: Vec<i32>, k: i32) -> i32 {
let mut min_len = i32::MAX;
let n = nums.len();
// 解决方案 1 的实现
for i in 0..n {
for j in (0..=i).rev() {
if is_special(&nums, j, i, k) {
min_len = cmp::min(min_len, (i - j + 1) as i32);
}
}
}
if min_len == i32::MAX {
-1
} else {
min_len
}
}
fn is_special(nums: &Vec<i32>, j: usize, i: usize, k: i32) -> bool {
let mut res = 0;
for idx in j..=i {
res |= nums[idx];
}
res >= k
}
fn minimum_subarray_length_optimized(nums: Vec<i32>, k: i32) -> i32 {
let mut min_len = i32::MAX;
let mut nums = nums.clone(); // 复制一份 nums
let n = nums.len();
for i in 0..n {
if nums[i] >= k {
return 1;
}
for j in (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) as i32);
}
} else {
break; // 提高效率，如果不再变化，则可直接跳出
}
}
}
if min_len == i32::MAX {
-1
} else {
min_len
}
}
fn main() {
let nums = vec![1, 2, 3];
let k = 2;
println!("{}", minimum_subarray_length(nums.clone(), k)); // 解决方案 1
println!("{}", minimum_subarray_length_optimized(nums, k)); // 解决方案 2
}
