#0001. 长度最小的子数组

原题

209. 长度最小的子数组

描述

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：
输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
进阶：
如果你已经完成了 O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

双指针

定义两个指针 start 和 end 分别表示子数组的开始位置和结束位置，维护变量 sum 存储子数组中的元素和(即从 nums[start] 到 nums[end] 的元素和)。
初始状态下，start 和 end 都指向下标 0，sum 的值为 0。
每一轮迭代，将 nums[end] 加到 sum，如果 sum≥s，则更新子数组的最小长度 (此时子数组的长度是 end−start+1)，然后将 nums[start] 从 sum 中减去并将 start 右移，直到 sum<s，在此过程中同样更新子数组的最小长度。在每一轮迭代的最后，将 end 右移。

func minSubArrayLen(s int, nums []int) int {
    length := len(nums)
    if length == 0 {
        return 0
    }
    ans := math.MaxInt32 // 定义结果为最大值
    start, end := 0, 0   // 双指针，左右边界
    sum := 0             // 求和，临时变量
    // 遍历数组
    for end < length {
        sum += nums[end]
        // 当 sum 大或等于目标 s 时，则更新子数组的最小长度（此时子数组的长度是 end-start+1），并减去 nums[start] ，将 start 右移
        for sum >= s {
            ans = min(ans, end-start+1)
            sum -= nums[start]
            start++
        }
        // sum 小于 s，将 end 右移
        end++
    }
    if ans == math.MaxInt32 {
        return 0
    }
    return ans
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

滑动窗口

在滑动窗口 [i,j]之间不断往后移动，如果总和小于 s，就扩大右边界 j，不断加入右边的值，直到 sum > s，之和再缩小 i 的左边界，不断缩小直到 sum < s，这时候右边界又可以往右移动。以此类推。

func minSubArrayLen(s int, nums []int) int {
    n := len(nums)
    if n == 0 {
        return 0
    }
    left, right, res, sum := 0, -1, n+1, 0
    for left < n {
        if (right+1) < n && sum < s {
            right++
            sum += nums[right]
        } else {
            sum -= nums[left]
            left++
        }
        if sum >= s {
            res = min(res, right-left+1)
        }
    }
    if res == n+1 {
        return 0
    }
    return res
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}