长春火车站附近美食,品牌建设与市场推广,金融网站建设网,钟表网站模板题目#xff1a;长度最小的子数组
描述#xff1a; 给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, …, numsr-1, numsr] #xff0c;并返回其长度。如果不存在符合条件的子数组长度最小的子数组
描述 给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, …, numsr-1, numsr] 并返回其长度。如果不存在符合条件的子数组返回 0 。
示例 1
输入target 7, nums [2,3,1,2,4,3] 输出2 解释子数组 [4,3] 是该条件下的长度最小的子数组。
leetcode链接 方法一滑动窗口 滑动窗口有两种一种是固定大小的窗口另一种是动态大小的窗口而本题要求长度最小的子数组所以应该用动态大小的窗口滑动窗口基于双指针的思想 我们定义两个指针left和right表示窗口的两端定义一个minLen变量表示最端短的长度初始时指针都指向0此时如果窗口内的数之和小于目标数target那么right指针右移窗口变大相反如果窗口内的数之和大于目标数target那么更新minLen,并且移动left指针直到窗口内的数之和小于目标数target为止。最后遍历完数组minLen即为长度最小的子数组 时间复杂度o(n) 空间复杂度o(1) int minSubArrayLen(int target, vectorint nums) {int n nums.size();int minLen n1;int left 0,right 0;int sum 0;while(rightn){sumnums[right];while(sumtarget){minLen min(minLen,right-left1);sum-nums[left];left;}right;}//如果minLen没有更新过即为不存在满足条件的子数组返回0return minLenn1?0:minLen;}方法二暴力法 我们枚举数组中的每一个元素为子数组的起始元素然后找到从枚举的元素开始满足条件的最小子数组的长度再维护最小的子数组长度即可找到答案。 时间复杂度o(n²) 空间复杂度o(1) int minSubArrayLen(int s, vectorint nums) {int n nums.size();if (n 0) {return 0;}int ans INT_MAX;for (int i 0; i n; i) {int sum 0;for (int j i; j n; j) {sum nums[j];if (sum s) {ans min(ans, j - i 1);break;}}}return ans INT_MAX ? 0 : ans;}方法三前缀和二分查找 暴力法中枚举子数组起始元素的时间复杂度为o(n),找到最小子数组的时间复杂度为o(n),此时我们考虑优化寻找最小子数组的时间注意到我们给定的数组的所有的元素都是大于0的那么我们每一个元素的前缀和都是递增的因此我们可以利用二分查找来查找最小子数组如果我们枚举第i个元素为最小子数组的起始元素那么我们二分查找的元素可以变为targeti的前缀和而此时找到的目标元素的前缀和-i的前缀和 target因此我们找到的元素即为最短子数组的末尾然后我们再维护最短的一个长度 时间复杂度o(nlogn) 二分查找的时间复杂度为logn 空间复杂度o(n) 存储前缀和的空间为o(n) 注意注意二分查找时的left和right指针的取值 int minSubArrayLen(int target, vectorint nums) {int n nums.size();int minLen n1,mid 0;vectorint sum(n1,0);//sum[i]表示前i个数之和 for(int i1;in;i){sum[i] sum[i-1]nums[i-1];}for(int i1;in;i){//枚举每个元素为子数组的起始元素//注意i为第i个元素而第i个元素的下标为i-1int tag targetsum[i-1];//这里的left和right表示的为第几个元素由于sum[i]为第i个元素的前缀和int left i,right n;while(leftright){mid (leftright)/2;if(tagsum[mid]){left mid1;}else{//我们要找的数为大于等于tag所以rightmid而不是mid-1right mid;}}if(sum[left]tag){minLen min(left-i1,minLen);}}return minLenn1?0:minLen;
}
