https://leetcode.cn/problems/minimum-size-subarray-sum/description/

<aside> 💡

思路重点：使用right作为循环条件，对于每个确定的right，移动left寻找该right值下的最优解（滑动窗口）

• right负责探索可能解
• left负责优化已有解

注意：left不用每次都从第一个开始重新遍历，而是接着上一次的位置往后走，所以实际上left和right各自都只遍历了一遍数组，时间复杂度是n+n，即O(n)，而非O(n^2)

</aside>

v1

// 维护两个指针，总和大于target则从左缩减范围，小于target则从右扩大范围
// 使用一个值ans来记录滑动过程中发现的最小长度
int minSubArrayLen0(int target, vector<int>& nums) {
	int left = 0, right = 0; 
	int sum;
	int ans = nums.size() + 1;
	if (nums.size() > 0)
		sum = nums[0];
	else
		return 0;

	while (right <= nums.size() - 1) {
		// right达到边界时，left还有缩减的可能
		if (right == nums.size() - 1 && sum < target)
			break;
		if (sum < target) {
			// 扩展右侧
			sum += nums[++right];
		} else {
			// 更新最小长度
			ans = ((right - left + 1) < ans) ? (right - left + 1) : ans;
			// 缩减左侧
			sum -= nums[left++];	
		}
	}
	return (ans == nums.size() + 1) ? 0 : ans;
}

v2——先扩张窗口再收缩窗口，

• 需要注意right的边界处理，右开的情况下，内外层循环中right的边界都是right < nums.size()

int minSubArrayLen(int target, vector<int>& nums) {
    int left = 0;
    int right = 1;
    int sum = nums[0];
    if (sum >= target) {
        return 1;
    }
    int ans = nums.size() + 1;

    // 窗口左闭右开
    while (right < nums.size()) {
        // 从右侧扩大窗口，right到达边界时只能进行收缩窗口操作
        while (right < nums.size() && sum < target) {
            sum += nums[right++];
        }
        // 从左侧收缩窗口
        while (left < right && sum >= target) {
            ans = std::min(ans, right - left);
            sum -= nums[left++];
        }
    }
    return (ans == nums.size() + 1) ? 0 : ans;
}

v3优化版——固定right，寻找当前right下的最优left

// 看代码随想录视频讲解改进后的写法
int minSubArrayLen(int target, vector<int>& nums) {
	int left = 0, right = 0;
	int sum = 0;
	int ans = nums.size() + 1;

	for (; right <= nums.size() - 1; ++right) {
		sum += nums[right];

		// 移动left，寻找right当前位置的最优解
		while (sum >= target) {
			ans = ((right - left + 1) < ans) ? (right - left + 1) : ans;
			sum -= nums[left++];
		}
	}
	return (ans == nums.size() + 1) ? 0 : ans;
}