织梦培训机构网站模板游戏推广员上班靠谱吗

前言

题目：209. 长度最小的子数组

参考答案：长度最小的子数组-力扣官方题解、长度最小的子数组-代码随想录

提交代码

暴力解

使用一个长度为step的窗口，在数组上滑动。比较窗口中的元素的和与target的大小。逐步增加step的大小，直到找到解。为了减少窗口中元素求和的计算量，这里使用前缀和进行优化。

#include <iostream>
#include <vector>using namespace std;class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {const int len = nums.size();// 计算前缀和vector<int> prefixSum(nums.size(),0);for(int i=1; i<len; i++)prefixSum[i] = prefixSum[i-1] + nums[i-1];prefixSum.push_back(prefixSum[len-1]+nums[len-1]); // 因为前缀和没法包含最后一个元素，这里修正下。所以前缀和比nums多一个元素// 时间复杂度为O((1+n)*n/2)=O(n^2)for(int step=1; step<=len; step++){for(int i=0; i+step<=len; i++){if(prefixSum[i+step]-prefixSum[i] >= target)return step;}}return 0;}
};int  main(void){int target = 7;vector<int> nums ={2,3,1,2,4,3};Solution s;cout<<s.minSubArrayLen(target,nums)<<endl;return 0;
}

双指针

上面代码的时间复杂度为$O(n^2)$。想要时间复杂度下降到$O(n)$。自然而然，会打起双指针的主意。这里使用快慢指针。快指针向前扩大范围，以使快慢指针之间的元素和大于target。慢指针向前缩小范围，以使范围的长度尽可能小。

上面的代码，有个地方看着不舒服，即前缀和的修正。一个变量/方法只干一件事情，如果希望修改它，应当使用适配器这样的思路。下面把求和的部分拎出来，便于优化。(我没有优化，因为优化的话，需要创建prefixSum成员变量和配套的方法，有些麻烦)

class Solution {
private:int sum(int start, int end, vector<int>& nums){// 计算[start,end]范围元素的和// 这个函数可以用前缀和函数进行优化。创建prefixSum为私有成员变量。return accumulate(nums.begin()+start,nums.begin()+end,nums[end]);}
public:int minSubArrayLen(int target, vector<int>& nums) {int i=0,j=0;const int len = nums.size();int minLen = len+1;for(; j<len; ){ if(i==j && nums[i]>=target) // 任何时候，慢指针i，不允许，在快指针j，前面；当相等的时候，说明范围内只有一个元素;如果这个元素大于target，直接返回1return 1;if(sum(i,j,nums) < target)j++; // 扩大范围else{minLen = minLen < j-i+1 ? minLen:j-i+1;i++;// 缩放范围：这里每次只所以一步；可以优化这里一次缩小多步}}return minLen > len ? 0:minLen;}
};