长度最小的子数组
题目描述
给定一个含有
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
}
}
Link
版权声明：本文为m0_56510407原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。