[LeetCode][Golang]|[LeetCode][Golang] 209. 长度最小的子数组 [LeetCode][Golang]209.长度最小的子

题目：给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0。

1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105

题解一： 滑动窗口可以很好的解决。先贴代码（Go）:

func minSubArrayLen(target int, nums []int) int { l, r, n, minValue := 0, 0, len(nums), math.MaxInt32 //[i,r] sum := 0 for r < n && l <= r { sum += nums[r] for sum >= target { minValue = https://www.it610.com/article/min(minValue, r-l+1) sum -= nums[l] l++ } r++ }if minValue == math.MaxInt32 { return 0 } return minValue }func min(a int, b int) int { if a < b { return a } return b }

核心思想是：

右移 r 时，子数组和变大，因此和不够时，右移 r。
右移 l 时，子数组长度变小，因此和足够时，左移 l。
当右移 r 使得子数组和满足条件时，立刻寻找符合条件的最右的 l 并记录。
当右移 l 使得子数组和不满足条件时，立刻寻找符合条件的最左的 r 并记录。

在不满足时优先满足条件，在满足条件时优先降低消耗（子数组长度），可谓是 贪心算法。
比暴力求解少遍历很多情况，例如：(n 为合适的正整数)

当我们知道 [l,r] 满足条件时，[l,r+n] 范围内的子数组不再考虑，因为它一定也满足条件但是比 [l,r] 更长。
当我们知道 [l,r] 不满足条件时，[l+n,r] 范围内的子数组不再考虑。因为它一定也不满足条件。

复杂度分析：
时间复杂度：O(n)，其中 n 是数组的长度。指针 l 和 r 最多各移动 n 次。
空间复杂度：O(1)。
题解二：题目在进阶中，有个奇怪的要求：如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。
好！很有精神！
其实就是为了锻炼下 前缀和 的方法，先贴代码（Go）：

func minSubArrayLen(s int, nums []int) int { n := len(nums) if n == 0 { return 0 } ans := math.MaxInt32 sums := make([]int, n+1) // 为了方便计算，令 size = n + 1 // sums[0] = 0 意味着前 0 个元素的前缀和为 0 // sums[1] = A[0] 前 1 个元素的前缀和为 A[0] // 以此类推 for i := 1; i <= n; i++ { sums[i] = sums[i-1] + nums[i-1] } for i := 0; i <= n; i++ { target := s + sums[i] bound := sort.SearchInts(sums, target) if bound <= n { ans = min(ans, bound-(i)) } } if ans == math.MaxInt32 { return 0 } return ans } func min(a int, b int) int { if a < b { return a } return b }

每个 sums 元素使用一次 二分搜索 ，成功将复杂度升到了 O(nlogn)。
至于 前缀和 的方法，Emmmmmmmm，以后再说，题目的奇怪要求，在这里使用，不合我意。
复杂度分析：
时间复杂度：O(nlogn)，其中 n 是数组的长度。需要遍历每个下标作为子数组的开始下标，遍历的时间复杂度是 O(n)，对于每个开始下标，需要通过二分查找得到长度最小的子数组，二分查找得时间复杂度是 O(logn)，因此总时间复杂度是 O(nlogn)。
【[LeetCode][Golang]|[LeetCode][Golang] 209. 长度最小的子数组】空间复杂度：O(n)，其中 n 是数组的长度。额外创建数组 sums 存储前缀和。