当前位置：首页 > news >正文

力扣原题《长度最小的子数组》，有序版(理想版最大值查找)纯手搓，已验证，方差版(考虑元素离散，大值周围全是小值的情况)在下一篇

news 2026/5/11 21:08:37

理想版，大值周围是大值

给定一个含有 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 <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 104

我的答案

classMinSubArray{public:MinSubArray(){}intminSubArrayLen(inttarget,vector<int>&nums){//先排序//std::sort(nums.begin(),nums.end());vector<int>::iterator maxPos=max_element(nums.begin(),nums.end());//双指针vector<int>::iterator left=nums.end();vector<int>::iterator right=nums.end();if(maxPos!=nums.begin()&&maxPos-1>=nums.begin()){left=maxPos-1;}if(maxPos+1<nums.end()){right=maxPos+1;}if(*(maxPos)>=target){return1;}else{intsum=*(maxPos);boolisTopLeft=false,isTopRight=false;//如果到头了，就不要重复加了while(true){inttag=0;if(left!=nums.end()&&right!=nums.end())//左右都存在{if(!isTopLeft&&*left>*right){sum+=*left;if(left!=nums.begin()){left--;tag=1;}else{isTopLeft=true;}}elseif(!isTopRight){sum+=*right;if(right<nums.end()){right++;tag=2;}else{isTopRight=true;}}}elseif(!isTopLeft&&left!=nums.end())//只有左边存在{sum+=*left;if(left!=nums.begin()){left--;tag=3;}else{isTopLeft=true;}}elseif(!isTopRight&&right!=nums.end())//只有右边存在{sum+=*right;if(right<nums.end()){right++;tag=4;}else{isTopRight=true;}}if(sum>=target){switch(tag)//避免重复加一个{case1:case3:if(left!=nums.begin()||!isTopLeft){left++;}break;case2:case4:if(right==nums.end()||!isTopRight){right--;}break;default:break;}break;}if((left==nums.end()&&right==nums.end())||(isTopLeft&&isTopRight)||(left==nums.end()&&isTopRight)||(right==nums.end()&&isTopLeft)){break;}}if(sum>=target){returnright-left;}return0;}return0;}};intmain(){vector<vector<int>>nums;vector<int>target;nums.push_back({2,3,1,2,4,3});nums.push_back({1,4,4});nums.push_back({1,1,1,1,1,1,1,1});nums.push_back({1,2,3,4,5});nums.push_back({12,28,83,4,25,26,25,2,25,25,25,12});target.push_back(7);target.push_back(4);target.push_back(11);target.push_back(15);target.push_back(213);MinSubArray minSubArray;for(vector<vector<int>>::iterator iter=nums.begin();iter!=nums.end();iter++){std::cout<<"最小子数组长度为:"<<minSubArray.minSubArrayLen(target[iter-nums.begin()],*(iter))<<std::endl;}}