长度最小的子数组
题目链接
题目：给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其总和大于等于 target 的长度最小的子数组，并返回其长度。如果不存在符合条件的子数组，返回 0 。
//我的方法:我不仅能求得最小子数组的长度，还能把最小子数组输出
#include<stdio.h>
int minArray(int nums[],int min[],int target,int length){int count=0;//用于记录每个子数组的长度int index=0;//用于记录数组的起始位置int sum=0;int temp=100;//用于记录最小子数组的长度 for(int i=0;i<=length;i++){//有等号是因为要判断加完最后一个元素后的和是否符合target if(sum<target){if(i==length)//加完最后一个元素还是比target小，直接跳出循环 break;sum+=nums[i];count++;}else{if(count<temp){//如果该子数组比之前的短，则覆盖原来的子数组 temp=count;index=i-count;} count=0;//重置值，进行下一轮判断 sum=0;i--;//因为此次循环结束i会+1 *****} } if(temp==100)//若没有子数组大于target return 0; for(int i=0;i<temp;i++)//把子数组放进创建的新数组中 min[i]=nums[index++];return temp;
}int main(){int nums[]={1,4,4};int length=sizeof(nums)/sizeof(nums[0]);int target;scanf("%d",&target);int min[length]={0};//创建一个新数组int k=minArray(nums,min,target,length);if(k==0)printf("0");elseprintf("%d\n",k); //输出最小子数组长度 for(int i=0;i<k;i++)printf("%d ",min[i]); //输出最小子数组
}最优方法：滑动窗口 学学学！！！
//滑动窗口，其实类似双指针思想
#include<stdio.h>
#include<limits.h>//为了使用INT_MAX
int minSubArrayLen(int target,int nums[],int numsSize){//初始化最小长度int minLength=INT_MAX;int sum=0;int left=0,right=0;//右边界向右扩展for(;right<numsSize;right++){sum+=nums[right];//*****当sum的值大于等于target时，保存长度，并且收缩左边界while(sum>=target){//*****************int subLength=right-left+1;minLength=minLength<subLength?minLength:subLength;//若要输出最小子数组，可以在上一句记录其头temp=left sum-=nums[left++];//***滑动窗口，减掉该子数组的头******} } return minLength==INT_MAX?0:minLength;
}
int main(){int nums[]={2,3,1,2,4,3};int numsSize=sizeof(nums)/sizeof(nums[0]);int target;scanf("%d",&target);int result=minSubArrayLen(target,nums,numsSize);printf("%d",result);
}