理解滑动窗口相比暴力解法减少的冗余是哪些

// 附录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, 我们是移除元素还是新增元素. => 应该是移除元素, 因为当前窗口的子数组已经是解了，那么是没有必要再检查 在此基础上添加新元素 而产生的新数组的.

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)
		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. https://coding.imooc.com/learn/questiondetail/45664.html

209. 长度最小的子数组

原文：https://www.cnblogs.com/yudidi/p/12772573.html