LeetCode209长度最小子数组
目录
LeetCode209长度最小子数组
思路①：暴力解，双重循环嵌套，遍历所有解找到最终答案，时间复杂度O（n²），超时pass
思路②：滑动窗口，也就是双指针，其实就是对双重循环的优化，把双重循环变成一次循环，降低时间复杂度到O(n)，其中i表示起始位置，j表示终止位置，当区间和小于target，j往后滑动，当区间和>=target，i往前滑动，最终找到满足条件的最小区间长度。
第一次编译没加上数组最大和的判断，在nums=[1,1,1,1,1,1,1,1]时没通过，所以在进入循环前可以加上一个数组最大和的判断，当最大和小于target时不符合条件直接return 0，当最大和等于target返回数组长度，当最大和大于target再进入循环找最小长度
int minSubArrayLen(int target, int* nums, int numsSize) {
//初始化最小长度为数组长度
int minL=numsSize;
int sum=0;//用于记录区间内的和
int i=0,j=0;//i记录初始位置，j记录终止位置
int k=0;
int Maxsum=0;
//先检查数组最大和是否满足>=target的条件
while(k<numsSize)
{
Maxsum+=nums[k++];
}
if(Maxsum<target) return 0;
if(Maxsum==target) return numsSize;
else
{
for(j=0;j<numsSize;j++)
{
sum+=nums[j];
while(sum>=target)
{
int L=j-i+1;//用于记录当前区间长度
if(L<minL)
{
minL=L;//若当前区间长度 小于最小长度，则更新最小长度为当前区间长度
}
sum-=nums[i++];
}
}
return minL;
}
}