leet Code [209. Minimum Size Subarray Sum]

[209. Minimum Size Subarray Sum][(https://leetcode.cn/problems/minimum-size-subarray-sum/)

暴力解法

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

class Solution {public:    int minSubArrayLen(int target, vector& 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 = 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& nums) {        int left = 0;//滑动窗口起始位置        int total = 0;//滑动窗口终止位置        int count = 0;//滑动窗口长度        int result = INT32_MAX;//最终长度值        for( int right = 0; right = target)            {                result = count < result ? count : result;                --count;                total -= nums[left++];            }        }        return result == INT32_MAX ? 0 : result;    }};

• 时间复杂度：O(n)

  空间复杂度：O(1)