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而已。

看不懂可以動手寫看看，或者再看看別人的其他解法～

明天會講線性資料儲存方式～