iT邦幫忙

2021 iThome 鐵人賽

DAY 5
0
Software Development

算法30天系列 第 5

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++。

看一下圖解,會比較清楚~
https://ithelp.ithome.com.tw/upload/images/20210911/20129767xXqKHImNlF.png
一開始sum+=2,還沒有大於7,所以再往下走
https://ithelp.ithome.com.tw/upload/images/20210911/20129767YB7nAXiYGt.png
sum+=3
https://ithelp.ithome.com.tw/upload/images/20210911/20129767AJDtehfsFX.png
sum+=2,注意這時候sum>=7了,算出來的長度是3
現在已經把start到end的區間統計完了,只要把start這位置往右移,就是一個新的區間。
sum-=nums[start],start++
https://ithelp.ithome.com.tw/upload/images/20210911/20129767W6HPGeqjmu.png
再重複這個邏輯
https://ithelp.ithome.com.tw/upload/images/20210911/20129767KujCKEJzZ9.png
https://ithelp.ithome.com.tw/upload/images/20210911/2012976754k92Q8zw5.png
最後會走到這一步
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而已。

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

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


上一篇
Day.4 Two Pointer
下一篇
Day.6 線性資料
系列文
算法30天30

尚未有邦友留言

立即登入留言