209. Minimum Size Subarray Sum
Medium
Given an array of positive integers nums
and a positive integer target
, return the minimal length of a
subarray whose sum is greater than or equal to target
. If there is no such subarray, return 0
instead.
Example 1:
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.
Example 2:
Input: target = 4, nums = [1,4,4]
Output: 1
Example 3:
Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0
Constraints:
1 <= target <= 10^9
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^4
Follow up: If you have figured out the O(n)
solution, try coding another solution of which the time complexity is O(n log(n))
.
解題
O(n) 的 solution, Sliding window
func minSubArrayLen(target int, nums []int) int {
res := 1000000
sum := 0
left := 0
for i:=0; i<len(nums); i++ {
sum += nums[i]
if sum >= target { // 加上去 window 右邊的值大於目標
for { //將 window 左邊一直右移(縮小 window) 直到不能再移(再移sum會小於目標)
if left >= 0 && sum-nums[left] >= target {
sum -= nums[left]
left++
} else {
break
}
}
res = min(res, i-left+1)
if res == 1 { return res } //除非無解,不然不會有比 1 更小的答案
}
}
if res==1000000 { //無解
return 0
}
return res
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
Last updated