两种解法解决LCR 008. 长度最小的子数组【C++】-Toy模板网

这篇具有很好参考价值的文章主要介绍了两种解法解决LCR 008. 长度最小的子数组【C++】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

LCR 008. 长度最小的子数组

两种解法解决LCR 008. 长度最小的子数组【C++】,算法刷题经验,c++,开发语言

解法

暴力解法

//暴力解法：
//使用双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;
    }
};