【滑动窗口】Leetcode 长度最小的子数组-算法讲解

算法1:暴力枚举

枚举出所有和大于等于target的数组,然后求出其中长度最小的那一个

class Solution {
public:
 int minSubArrayLen(int target, vector<int>& nums) {
 	// 记录结果
 	int ret = INT_MAX;
	int n = nums.size();
 // 枚举出所有满⾜和⼤于等于 target 的⼦数组[start, end]
 // 由于是取到最⼩,因此枚举的过程中要尽量让数组的⻓度最⼩
 // 枚举开始位置
 for (int start = 0; start < n; start++)
 {
 	int sum = 0; // 记录从这个位置开始的连续数组的和
	 // 寻找结束位置
 	for (int end = start; end < n; end++)
	 {
 		sum += nums[end]; // 将当前位置加上
 		if (sum >= target) // 当这段区间内的和满⾜条件时
	 	{
 			// 更新结果,start 开头的最短区间已经找到
 			ret = min(ret, end - start + 1);
			break;
 		}
 	}
 }
 	// 返回最后结果
 	return ret == INT_MAX ? 0 : ret;
 }
};

算法2:滑动窗口

从数组的起始位置开始,我们每一次+=上当前位置的nums[i],然后判断当前的总和是否满足条件。如果满足就让左边的数字出窗口,然后窗口变小;如果当前的总和不满足,继续让窗口变大

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        //看到这道题典型的使用滑动窗口
        int left = 0, right = 0;
        int len = INT_MAX;
        int sum = 0;
        while(right < nums.size())
        {
            sum += nums[right];
            while(sum >= target)
            {
                len = min(len, right - left + 1);
                //左边的数字出窗口
                sum -= nums[left++];
            }
            right++;
        }
        if(len == INT_MAX)return 0;
        return len;
    }
};

为什么要使用滑动窗口?因为我们看到这道题的要求就是需要一段区间的数值,然后这个区间的的大小一直是不知道的,每次取的是区间右边的第一个数字,不要的是区间左边的第一个数字,并且区间一旦不满足左边的第一个数字也就是不需要了。所以说就是需要滑动窗口来解决这种问题


上一篇:vim 配置显示行号 tab缩进-2. 配置


下一篇:ubuntu出现WARNING: perf not found for kernel 5.15.0-41的解决方法