• 209.长度最小的子数组

    代码：（详细注释）

    1. //暴力解法O(n^2)
    2. class Solution {
    3. public:
    4.     int minSubArrayLen(int s, vector<int>& nums) {
    5.         int result = INT32_MAX; // 最终的结果，INT32_MAX只是用来赋初始值
    6.         int sum = 0; // 子序列的数值之和
    7.         int subLength = 0; // 子序列的长度
    8.         for (int i = 0; i < nums.size(); i++) { // 设置子序列起点为i
    9.             sum = 0;
    10.             for (int j = i; j < nums.size(); j++) { // 设置子序列终止位置为j
    11.                 sum += nums[j]; //🤳关键一步，在子序列中累加
    12.                 if (sum >= s) { // 一旦发现子序列和超过了s，更新result
    13.                     subLength = j - i + 1; // 取子序列的长度
    14.                     result = result < subLength ? result : subLength;
    15.                     break; // 因为我们是找符合条件最短的子序列，所以一旦符合条件就break，这时候已经是最小的长度了
    16.                 }
    17.             }
    18.         }
    19.         // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
    20.         return result == INT32_MAX ? 0 : result;
    21.     }
    22. };
    1. //滑动窗口 O(n)
    2. class Solution {
    3. public:
    4.     int minSubArrayLen(int s, vector<int>& nums) {
    5.         int result = INT32_MAX;
    6.         int sum = 0; // 滑动窗口数值之和
    7.         int i = 0; // 滑动窗口起始位置
    8.         int subLength = 0; // 滑动窗口的长度
    9.         for (int j = 0; j < nums.size(); j++) {
    10.             sum += nums[j];//🤳关键一步，在子序列中累加
    11.             // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
    12.             while (sum >= s) {
    13.                 subLength = (j - i + 1); // 取子序列的长度
    14.                 result = result < subLength ? result : subLength;
    15.                 sum -= nums[i++]; // 🤳这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
    16.             }
    17.         }
    18.         // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
    19.         return result == INT32_MAX ? 0 : result;
    20.     }
    21. };

    分析：