长度最小的子数组
题目描述
给定一个含有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
思路
题目要求
- 给定一个数组和一个正整数，找到最小子数组的和
≥给定的正整数 - 返回最小子数组的长度，若不存在则返回
0
暴力解法是写两个for循环，然后不断的寻找符合条件的子序列，时间复杂度很明显是O(n^2)
滑动窗口法：不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。定义一个左指针和一个右指针，右指针向前移动，直到找到子串和大于给定数停止移动，并记录子串长度。此时，左指针向前移动，找子串的最小长度并记录。当子串和小于给定数时，左指针停止移动，右指针开始向前移动，直到找到子串和大于给定数停止移动……这样可以将数组中所有可能性都计算一遍。时间复杂度是O(n)。
滑动窗口法也可以理解为双指针法的一种，只不过这种解法更像是一个窗口的移动，所以叫做滑动窗口更适合一些。
注意
- 左右指针的起始位置都置为
-1，与后面先移动指针后累加的顺序保持一致 - 为了与后面比较各子串长度，所以将最小子串初值置为数组长度+1，最后返回最小子串长度进行判断
- 循环条件为左指针不超过右指针，当右指针移动后越界也结束循环
代码
Go
func minSubArrayLen(target int, nums []int) int { length := len(nums) leftIndex, rightIndex := -1, -1 minSubLen := length + 1 sum := 0 for leftIndex <= rightIndex { if sum < target { rightIndex++ if rightIndex > length-1 { break } sum += nums[rightIndex] } else { leftIndex++ if rightIndex-leftIndex+1 < minSubLen { minSubLen = rightIndex - leftIndex + 1 } sum -= nums[leftIndex] } } if minSubLen == length+1 { return 0 } else { return minSubLen } }
