目录
1.题目
2.分析
方法1:暴力枚举
方法2:暴力枚举的优化:"同向双指针",也称滑动窗口
前置知识
核心操作
例子解释
代码
提交结果
1.题目
LCR 008. 长度最小的子数组
给定一个含有
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提示：
1 <= target <= 10^91 <= nums.length <= 10^51 <= nums[i] <= 10^5进阶：
- 如果你已经实现
O(n)时间复杂度的解法, 请尝试设计一个O(n log(n))时间复杂度的解法。注意：本题与主站 209 题相同：209. 长度最小的子数组 - 力扣（LeetCode）
2.分析
方法1:暴力枚举
第一层循环:枚举连续子数组的长度len,从1到nums.size()
第二层循环:对于每个len,可能有多个子数组,按子数组首元素的下标来枚举
第三层循环:计算子数组中元素的和,如果找到一个sum>=target,直接返回len
时间复杂度为
以[2,3,1,2,4,3]为例分析:
len==1: [2],[3],[1],[2],[4],[3]
len==2: [2,3],[3,1],[1,2],[2,4],[4,3]
len==3: [2,3,1],[3,1,2],[1,2,4],[2,4,3]
len==4: [2,3,1,2],[3,1,2,4],[1,2,4,3]
len==5: [2,3,1,2,4],[3,1,2,4,3]
len==6: [2,3,1,2,4,3]
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {for (int len=1;len<=nums.size();len++){for (int i=0;i+len<=nums.size();i++){//计算子数组的和unsigned long long sum=0;for (int j=i;j<i+len;j++)sum+=nums[j];if (sum>=target)return len;}}return 0;}
};提交结果:代码的时间复杂度为,显然当数据量较大时会超时
方法2:暴力枚举的优化:"同向双指针",也称滑动窗口
前置知识
给定闭区间[left,right],left为区间左边界,right为区间的右边界
由于题目给出"给定一个含有 n 个正整数的数组",数组中元素都是正整数,则right变大时,区间的元素和也变大,则可以利用区间的元素和的单调性写"滑动窗口",这样就规避掉方法1没有必要的枚举行为
核心操作
将[left,right]之间连续的元素视为窗口
进窗口:right++,让新元素进入窗口
出窗口:left++,让旧元素离开窗口
例子解释
在遍历的同时去求和,类似前缀和思想,仍然以[2,3,1,2,4,3],target = 7为例说明:
设len存储返回值,left给出左边界,将left固定,right从左边界向后枚举,right每指向一个新数,就为sum加上这个新数(思想类似前缀和,比方法1每次循环重新计算一遍sum要快)
一开始各个变量的初始值:
int left=0;
int right=0;
int sum=nums[0];
int len=10001;注:len初始化为10001的原因:题目"1 <= nums.length <= 10^5",len设置成比nums.length稍大的数就行了
(红色区域为滑动窗口)
如果sum<target,right++,为"进窗口"(新数据进入窗口),同时sum加上对应的值
if (sum<target)
{right++;if (right==nums.size())break;sum+=nums[right];
}
此时sum>target,记录len的值:right-left+1==4,但这个len不一定是最小值,因此要继续"滑动"窗口
注意:此时没有必要继续right++,因为sum已经大于target,题目要求最小值
left++,为"出窗口"(移除旧数据)sum减去对应的值,注意right不用回退,要利用区间的元素和的单调性
if (sum>=target)
{len=min(len,right-left+1);sum-=nums[left];left++;
}
sum<target,"进窗口"
sum>target,窗口长度为4,取len=min(len,right-left+1),之后"出窗口"
sum>target,窗口长度为3,取len=min(len,right-left+1),之后"出窗口"
sum<target,"进窗口"
sum>target,窗口长度为3,取len=min(len,right-left+1),之后"出窗口"
sum==target,窗口长度为2,取len=min(len,right-left+1),之后"出窗口"
sum<target,但right已经到头了,因此结束循环,返回len,则可得出循环的框架:
while (right<nums.size())
{//do_something
}
"同向双指针":left和right向同一个方向移动
时间复杂度:right最多移动到nums.size()-1处,时间复杂度为
代码
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int left=0;int right=0;int sum=nums[0];int len=100001;while (right<nums.size()){if (sum<target){right++;if (right==nums.size())break;sum+=nums[right];}else//sum>=target{len=min(len,right-left+1);sum-=nums[left];left++;}}if (len==100001)return 0;elsereturn len;}
};提交结果
