Day.5 Slide Window

Leetcode #209. Minimum Size Subarray Sum

简单来说题目会给一组array、数值target，寻找可加总>=target的长度最小连续数，并回传长度。
ex1:
Input: target = 7 , nums = [2,3,1,2,4,3]
Output: 2

2+3+1+2 = 8 >= 7 连续数为4
1+2+4 = 7 >= 7 连续数为3
4+3 = 7 >= 7 连续数为2
2是最小连续数，所以回传2

ex2:
Input: target = 4, nums = [1,4,4]
Output: 1

如果你没做过这题，强烈建议你先思考一下怎麽解。

防雷
防雷
防雷

这一题最直觉可以用暴力解，用nums去跑两次的回圈，每次都把往右的数值加总一轮，全部算完，就可以统计出那一个长度最短。这样的时间复杂度为O(n^2)。

那有没有更聪明的做法？
介绍大家Slide Window的算法

ex. target = 7, nums = [2,3,2,5]

多一个变数sum去记下加总数，start去记下区间起始的位置，只要在sum在 < target的情况下，都把数值累加到sum。
如果sum >= target，就重复把sum -= nums[start]，start++。

看一下图解，会比较清楚～

一开始sum+=2，还没有大於7，所以再往下走

sum+=3

sum+=2，注意这时候sum>=7了，算出来的长度是3
现在已经把start到end的区间统计完了，只要把start这位置往右移，就是一个新的区间。
sum-=nums[start]，start++

再重复这个逻辑


最後会走到这一步
2+5 >= 7
最小长度为2

程序:

func minSubArrayLen(target int, nums []int) int {
	start := 0
	sum := 0
	min := len(nums) + 1

	for i, v := range nums {
		sum += v
		for sum >= target {
			count := i - start + 1
			if min > count {
				min = count
			}

			sum -= nums[start]
			start++
		}
	}

	if min == len(nums)+1 {
		return 0
	}

	return min
}

这也是leetcode常见解巧，时间复杂度为O(n)，不要看到两个for回圈就以为一定是O(n^2)，中间那一个回圈跑的次数上限就一个n而已。

看不懂可以动手写看看，或者再看看别人的其他解法～

明天会讲线性资料储存方式～