209. 长度最小的子数组

leecode原题

题目

给定一个含有 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 <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

进阶：

如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(nlog(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循环遍历, 然后判断该窗口内的总和值是否>=目标值, 不是的话，那么窗口尾索引需要继续向前移动；是的话，我们就需要动态调整该窗口, 将窗口起始索引向前移动一位，然后继续判断，重复该过程。

实现

滑动窗口法

源码

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
}