209. 长度最小的子数组 暴力解 暴力解第一种优化(海哥) TODO 暴力解第二种优化 二分查找解法 (基于暴力解第二种优化) 滑动窗口 Q&A 优化 参考
O(n3)
暴力解第一种优化(海哥) TODO
去掉第3层循环
func minSubArrayLen(s int, nums []int) int {
// map k:i+j-1 v:sum[i,j-1] // sum[i,j] = sum[i,j-1]+num[j]
has := false
min := 100000
n := len(nums)
for i:=0;i<n;i++{ // [1,2,3] [2,3]
sum := nums[i]
for j:=i;j<n;j++{
if j > i{
sum += nums[j]
}
if sum >=s && j-i+1 < min{
min = j-i+1
has = true
break
}
}
}
if !has {
return 0
}
return min
}
暴力解第二种优化
二分查找解法 (基于暴力解第二种优化)
sums数组是有序数组
滑动窗口
Q&A
理解滑动窗口相比暴力解法减少的冗余是哪些
// 附录1
// 暴力解
func minSubArrayLen(s int, nums []int) int {
// [0,n-1][0,n-1]
n := len(nums)
min := 10000
// [i,j]
for i := 0; i < n; i++ {
for j := i; j < n; j++ {
fmt.Print(fmt.Sprintf("[%d,%d]", i, j))
sum := 0
for t := i; t <= j; t++ {
sum += nums[t]
}
if sum >= s && j-i+1 < min {
min = j - i + 1
break // i开头的最短满足条件的子数组,不需要再继续检查在该子数组基础上添加新元素的新子数组了
}
}
fmt.Println()
}
if min == 10000 {
return 0
}
return min
}
// 滑动窗口
// https://coding.imooc.com/learn/questiondetail/45664.html
func minSubArrayLen2(s int, nums []int) int {
n := len(nums)
min := 10000
l, r := 0, -1 // [l,r]
sum := 0
for l < n-1 {
fmt.Println(fmt.Sprintf("[%d,%d]", l, r), sum)
if sum >= s { // bug: sum > s {
sum -= nums[l]
l++
} else {
if r+1 < n {
r++
sum += nums[r]
}
}
if sum >= s && r-l+1 < min {
min = r - l + 1
}
}
if min == 10000 {
return 0
}
return min
}
// TODO 难点: 理解为什么滑动窗口不会漏掉一些情况.
func main() {
minSubArrayLen(7, []int{2, 3, 1, 2, 4, 3})
fmt.Println(">>>> 滑动窗口需要验证的子数组")
minSubArrayLen2(7, []int{2, 3, 1, 2, 4, 3})
}
// output
//[0,0][0,1][0,2][0,3]
//[1,1][1,2][1,3][1,4][1,5]
//[2,2][2,3][2,4]
//[3,3][3,4][3,5]
//[4,4][4,5]
//[5,5]
//>>>> 滑动窗口需要验证的子数组
//[0,-1] 0
//[0,0] 2
//[0,1] 5
//[0,2] 6
//[0,3] 8 // ① [0,3] 里面是包含了[0,3]的全部子数组的,比如[1,1][1,2][1,3] // 就是说，0开头的情况已经遍历完了,[0,3]的所有子数组(1/1,1/2,1/3,2/3,3/3)
//[1,3] 6 // ② ③ ④ Q: 为什么sum>s时,需要去掉0,需要担心漏掉1开头的子数组的解的情况吗? 不用,1开头的可能解已经检查完了.
//[1,4] 10
//[2,4] 7
//[3,4] 6
//[3,5] 9
//[4,5] 7
Q: 如何理解从①->②, 一次就可以排除5个子数组(1/1,1/2,1/3,2/3,3/3)。
A: 因为如果已经知道一个连续子数组的和小于s, 就没有必要去检查这个子数组中的其他子数组了。// 附录1
可能你会有疑问,这样排除子数组,会不会导致漏掉一些情况? 请看下一个问题:
Q: 从①->②, 为什么sum>s时,可以去掉0, 这样去掉不会漏掉某些解吗(漏掉1开头的子数组的解的情况)?
A: 不会漏掉解, 因为1开头的可能解已经检查完了.
Q: 下面这个bug来自sums时，没有移除元素，也没有添加元素，导致的无限循环。// 没有思考清楚sums的情况 + 编码习惯 => 共同导致的问题
A: sum==s时,需要移除元素.
下面代码的bug在哪里
滑动窗口解法，当窗口的sum==s, 我们是移除元素还是新增元素. => 应该是移除元素, 因为当前窗口的子数组已经是解了，那么是没有必要再检查 在此基础上添加新元素 而产生的新数组的.
YC: sum和s的比较这一段代码，如果按照sum>s和sum<s的先后顺序不同, 有2种写法，其中一种顺序容易漏掉情况。
写法1.1
func main() {
minSubArrayLen2(7, []int{2, 3, 1, 2, 4, 3})
}
func minSubArrayLen2(s int, nums []int) int {
n := len(nums)
min := 10000
l, r := 0, -1 // [l,r]
sum := 0
for l < n-1 {
fmt.Print(fmt.Sprintf("[%d,%d]", l, r), sum)
// 写法1, 死循环, 1[1], sum==s导致
if sum > s {
sum -= nums[l]
l++
} else {
if r+1 < n {
r++
sum += nums[r]
}
}
if sum >= s && r-l+1 < min {
min = r - l + 1
}
}
if min == 10000 {
return 0
}
return min
}
写法1.2: 增加sum==s时,移除元素的逻辑. 仍有死循环.
if sum >= s { // tia
sum -= nums[l]
l++
} else {
if r+1 < n {
r++
sum += nums[r]
}else{
break
}
}
写法1.3 没有bug
if sum >= s {
sum -= nums[l]
l++
} else if r+1 < n {
r++
sum += nums[r]
} else {
break
}
写法1.4 没有bug，类似写法1.4
if sum >= s {
sum -= nums[l]
l++
} else {
if r+1 < n {
r++
sum += nums[r]
} else {
break
}
}
顺序2:
if sum < s && r+1 < n {
r++
sum += nums[r]
}else{ // 之前我只关注了sum>=s时才移除左侧元素。现在看来少考虑了一种情况，就是不管sum大于或小于s, 只要不能右滑时，也是需要移除左侧元素的。
sum -= nums[l]
l++
}
优化
顺序1的写法1.3/1.4，有3个情况，其中break情况，是sum<s，但是已经不能右滑了，这种情况直接退出循环。
顺序2的写法，对于上述情况还是会不断剔除左侧元素，直到l==n-1, 做了无用功。
所以顺序1的性能会更好些。