深圳微信商城网站设计价格,网站开发ipv6升级,网站建设论文,百度推广网站谁做LeetCode_209 长度最小的子数组 LeetCode_209 长度最小的子数组 题目要求 给定一个含有 n** 个正整数的数组和一个正整数 target 。** 找出该数组中满足其总和大于等于target 的长度最小的 连续子数组[numssubl/sub, numssubl1/sub, ..., nums…LeetCode_209 长度最小的子数组 LeetCode_209 长度最小的子数组 题目要求 给定一个含有 n** 个正整数的数组和一个正整数 target 。** 找出该数组中满足其总和大于等于target 的长度最小的 连续子数组[numssubl/sub, numssubl1/sub, ..., numssubr-1/sub, numssubr/sub] 并返回其长度**。**如果不存在符合条件的子数组返回 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 10sup9/sup1 nums.length 10sup5/sup1 nums[i] 10sup5/sup
思路
使用滑动窗口法双指针slow和fast分别指示窗口的左右边界首先快指针开始右移慢指针不动同时求和sum开始累加直到碰到sumtarget开始考虑 最小 子序列的问题慢指针尝试右移以缩小窗口大小
代码与解析
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {// 初始化慢指针和快指针分别指向数组的开始位置int slow 0;int fast 0;// 初始化当前子数组的和为0int sum 0;// 初始化最小子数组长度为数组长度加1这是为了确保最小长度一定小于数组长度int minLength nums.size() 1;// 使用快慢指针法遍历数组while(fast nums.size() fast slow){// 快指针向前移动将当前元素加入到当前子数组的和中sum nums[fast];// 当当前子数组的和大于或等于目标值时开始尝试缩小子数组的长度while(sum target slow fast){// 更新最小子数组长度minLength minLength (fast - slow 1) ? (fast - slow 1) : minLength;// 如果最小长度已经为1则不需要继续寻找更小的子数组直接跳出循环if(minLength 1){break;}// 慢指针向前移动将当前元素从当前子数组的和中减去sum - nums[slow];// 慢指针向前移动slow ;}// 快指针向前移动fast ;}// 如果最小长度仍然为初始值说明没有找到满足条件的子数组返回0// 否则返回最小子数组长度return (minLength (nums.size() 1)) ? 0 : minLength;}
};方法和思想
快慢指针法使用两个指针一个快指针用于扩大子数组的范围一个慢指针用于缩小子数组的范围以此来找到满足条件的最小子数组。滑动窗口这种方法实际上是滑动窗口的一种应用通过调整窗口的大小来找到满足条件的最小窗口。
时间复杂度
时间复杂度O(n)其中 n 是数组的长度。因为每个元素最多被访问两次一次是快指针扫描一次是慢指针缩小窗口。
空间复杂度
空间复杂度O(1)因为只使用了几个固定的变量与输入数组的大小无关。
