题目
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例
示例1:
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例2:
输入：target = 4, nums = [1,4,4]
输出：1
示例3:
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
提示
- 1 <= target <= 10^9
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^4
进阶
如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。
解题思路
1.暴力破解法
这是我们很容易想到的一种解法, 即写两层for循环, 第一层循环是代表子序列开始位置for i:=0; i<len(arr);i++, 第二层循环是代表子序列结束位置for j:=i;j<len(arr);j++, 然后判断该子序列数组之和和目标值的大小判断。
2.滑动窗口法
所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。
如何只使用一个for循环就完成？
比如数组[2, 3, 1, 2, 4, 3], 我们以窗口尾索引进行第一层for循环遍历, 然后判断该窗口内的总和值是否>=目标值, 不是的话，那么窗口尾索引需要继续向前移动；是的话，我们就需要动态调整该窗口, 将窗口起始索引向前移动一位，然后继续判断，重复该过程。
实现
滑动窗口法
package main
import "fmt"
// 滑动窗口
func minSubArrayLen(target int, nums []int) int {
var (
size = len(nums)
window_sum = 0 //窗口值的综合
min_window_length = size + 1 //最小的窗口长度, 初始化可以初始化为数组长度+1
window_start_index = 0 // 窗口开始索引
window_end_index = 0 // 窗口结束索引
found = false
)
for window_end_index = 0; window_end_index < size; window_end_index++ {
window_sum += nums[window_end_index]
// 如果滑动窗口总和超过目标值, 那么就不停的动态调整窗口开始位置
for window_sum >= target {
found = true
window_length := window_end_index - window_start_index + 1
if window_length < min_window_length {
min_window_length = window_length
}
// 滑动窗口向前移动一位
window_sum -= nums[window_start_index]
window_start_index += 1
}
}
if found {
return min_window_length
}
return 0
}
func main() {
fmt.Println(minSubArrayLen(7, []int{2, 3, 1, 2, 4, 3}))
fmt.Println(minSubArrayLen(4, []int{1, 4, 4}))
fmt.Println(minSubArrayLen(11, []int{1, 1, 1, 1, 1, 1, 1, 1}))
}
