[209. Minimum Size Subarray Sum]

[(https://leetcode.cn/problems/minimum-size-subarray-sum/)

暴力解法

• 两个for循环，不断寻找符合条件的子序列

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int result = INT32_MAX; // 最终的结果
        int total = 0; // 子序列的数值之和
        int count = 0; // 子序列的长度
        for (int i = 0; i < nums.size(); i++) { // 设置子序列起点为i
            total = 0;
            for (int j = i; j < nums.size(); j++) { // 设置子序列终止位置为j
               total += nums[j];
                if (total >= target) { // 一旦发现子序列和超过了s，更新result
                    count = j - i + 1; // 更新子序列的长度
                    result = result < subLength ? result : subLength;
                    break; // 因为是找符合条件最短的子序列，所以一旦符合条件就break
                }
            }
        }
        // 返回0，说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }
};

• 时间复杂度：O(n^2)

  空间复杂度：O(1)

滑动窗口

• 所谓滑动窗口：不断调节子序列起始位置和终止位置，从而得出想要的结果。
• 在暴力解法中，我们使用了两个for循环，若用滑动窗口如何以一个for循环得出结果呢？
• 思路：
  • 首先，一个for循环是用来表示滑动窗口的起始位置，还是终止位置？若是表示起始位置，其实看着和暴力解法相差无几。因此for循环应该用来表示终止位置
  • 三个重点：
    • 滑动窗口内表示的是什么？
      • 窗口其实就是一个满足条件的连续子数组
    • 滑动窗口如何移动起始位置？
      • 若窗口内总值sum大于target，则需要向前移动起始位置
    • 滑动窗口如何移动终止位置？
      • 若窗口内sum小于target，则需要向前移动终止位置

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0;	//滑动窗口起始位置
        int total = 0;	//滑动窗口终止位置
        int count = 0;	//滑动窗口长度
        int result = INT32_MAX;		//最终长度值
        for( int right = 0; right < nums.size(); )		//for循环控制终止位置
        {
            total += nums[right++];
            ++count;
            
            //滑动窗口精髓
            while(total >= target)
            {
                result = count < result ? count : result;
                --count;
                total -= nums[left++];
            }
        }
        return result == INT32_MAX ? 0 : result;
    }
};

• 时间复杂度：O(n)

  空间复杂度：O(1)