LCR 008. 长度最小的子数组

解法

暴力解法

//暴力解法：
//使用双for循环依次遍历数组，罗列出所有情况，然后判断
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {//  (min_length < j-i+1)因为下面进行比较的时候新长度更小才会进行更新，所以置为//  最大的值又不超出数组元素的最大取值int min_length = INT_MAX;int sum = 0;int size = nums.size();for(int i=0; i<size; i++){sum=0;  //sum置零容易遗忘，切记for(int j=i; j<size; j++){sum += nums[j];//依次相加，直到第一次sum大于target为止if(sum >= target){//取最小长度min_length = (min_length < j-i+1) ? min_length : j-i+1;break;  //当大于目标值以后，也就不需要继续比较了}}}//  如果min_length一次也没有用更新就返回零return min_length == INT_MAX ? 0 : min_length;}
};

滑动窗口（双指针法）

//  滑动窗口法
//  窗口的起始位置cur移动规则：当子数组之和sum大于target时，cur++并且记录此时子数组的长度
//  窗口的终点位置dest移动规则： 当子数组之和sum小于target时，dest++class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int dest = 0; //    指向窗口终点int cur = 0;//  指向窗口起点int size = nums.size();int sum = 0;int min_length = INT_MAX;//循环结束条件应当是dest遍历完数组并且窗口已经缩短到最小状态(这个放在二层循环里面更为合适)while(dest < size){sum+=nums[dest];//一种情况就是sum>=target，此时并不能直接结束缩短窗口，min_length//还可能更小，所以再套一层循环while(sum >= target){min_length = dest-cur+1 < min_length ? dest-cur+1 : min_length;//窗口缩短一次，sum也一定要更新sum -= nums[cur];cur++;}dest++;}return min_length == INT_MAX ? 0 : min_length;}
};