未分類

Minimum Size Subarray Sum

Array, BinarySearch, Go, LeetCode, TwoPointers

Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

For example:

Given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

提示 解題應用
TwoPointers 紀錄index位置

Default:

1
2
3
func minSubArrayLen(s int, nums []int) int {
}

解答思路:

要從一陣列中找出最小子陣列且其總合大於等於目標值，只要一邊遍歷(當作子陣列的結尾)一邊計算目前陣列總和，如果發現將子陣列開頭向後推其總合仍能大於等於目標值，就一路推到不在大於等於目標值為止，此時再判斷如果目標子陣列長度小於最小長度就將其取代，最後待全數陣列遍歷完畢才向上回傳找出的最小長度。

程式碼解說:

一開始先將最小長度設為陣列長度，接著就開始一邊遍歷一邊計算目前陣列總和，如果總合大於等於目標值，又剛好子陣列開頭向後推其總合仍能大於等於目標值，就一路推到不在大於等於目標值為止，此時再判斷目標子陣列長度是否小於最小長度，是的話就將其取代，最後待全數陣列遍歷完畢如果發現總合仍小於目標值便回傳0，否則才向上回傳找出的最小長度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var sum int
var front int
minSize := len(nums)
for i, v := range nums {
	sum += v
	if sum >= s {
		for sum-nums[front] >= s {
			sum -= nums[front]
			front++
		}
		if i-front+1 < minSize {
			minSize = i - front + 1
		}
	}
}
if sum < s {
	return 0
}
return minSize

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func minSubArrayLen(s int, nums []int) int {
	var sum int
	var front int
	minSize := len(nums)
	for i, v := range nums {
		sum += v
		if sum >= s {
			for sum-nums[front] >= s {
				sum -= nums[front]
				front++
			}
			if i-front+1 < minSize {
				minSize = i - front + 1
			}
		}
	}
	if sum < s {
		return 0
	}
	return minSize
}

總結:

要從一陣列中找出最小子陣列且其總合大於等於目標值，只要一邊遍歷(當作子陣列的結尾)一邊計算目前陣列總和，如果發現將子陣列開頭向後推其總合仍能大於等於目標值，就一路推到不在大於等於目標值為止，此時再判斷如果目標子陣列長度小於最小長度就將其取代，最後待全數陣列遍歷完畢才向上回傳找出的最小長度。

分享到