1.题目1：209. 长度最小的子数组

1.1.解法1：暴力解法（已超时）

使用两层循环，外层循环确定最小子数组开始的位置（i），内层循环确定最小子数组结束的位置（j）。在每次跳出内层循环时，sum应重置为0。
当找到的子数组相加的和等于或大于目标值（target）时，算出此刻子数组的长度（j - i + 1），并更新result的值。
最终在外层循环遍历完所有元素时，对result值进行比较，如果result的值没有发生变化，则不存在符合条件的子数组，返回0。

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size(), res = INT_MAX;
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += nums[j];
                if (sum >= target) {
                    res = min(res, j - i + 1);
                    break;
                }
            }
        }
        return res == INT_MAX ? 0 : res;
    }
};

● 时间复杂度：\(O(n^2)\)
● 空间复杂度：\(O(1)\)

1.2.解法2：滑动窗口

让i最开始时指向数组起始位置（窗口起始位置），当子数组和大于目标值时，确定窗口的终止位置（j）。将窗口进行缩小，即将i所指位置向前推，相应sum减去i之前元素的值。
举个例子：
nums = [1,1,1,1,100]，target = 100。
当j指向100时，开始缩小窗口。i增大，sum减去1、1、1、1。

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int res = INT_MAX; 
        int i = 0; // 滑动窗口起始位置
        int sum = 0; // 滑动窗口数值之和
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
            // 每次更新i，比较子序列是否符合要求
            while (sum >= target) {
                res = min(res, j - i + 1); // 取子序列长度
                sum -= nums[i++];
            }
        }
        // 若res没有被赋值，返回0，没有符合条件的子序列
        return res == INT_MAX ? 0 : res;
    }
};

● 时间复杂度：\(O(n)\)
● 空间复杂度：\(O(1)\)

2.题目2：904.水果成篮

2.1.解法1：滑动窗口

这题与209的思考过程非常相似，但比较有意思的是使用了unordered_map，它与209中的sum使用方法是类似的。
简述我的思考过程：
据题意，只能保留两个类型的水果，并且需要连续收集尽可能多的水果数量。（即为只出现两个数字且长度最大的连续子数组）。
为了统计当前遍历到的水果类型的数目，使用unordered_map来进行统计：<水果类型，该类型水果数目>，记为unordered_map<int, int>t。
我们设置一个指针j，一直遍历数组，另一个指针i，指向数组的起始位置。
当j遍历时，将水果加入t中，t[fruit[j]]++，fruit[j]为水果类型，t[fruit[j]]为当前统计的该类型水果的数目。
一旦当t.size()大于2时，我们需要将i所指水果减去，更新i所指位置，直至该窗口中仅包含两种类型的水果，j才继续向后遍历。
res始终记录窗口最大长度：res = max(res, j - i + 1)。

在本题中实现滑动窗口，主要确定如下三点：
● 窗口内是什么？
● 如何移动窗口的起始位置？
● 如何移动窗口的结束位置？
窗口就是：只出现两个数字且长度最大的连续子数组。
窗口的起始位置如何移动：如果水果类型（unordered_map中元素）大于2，窗口就要向前移动，使得类型仍为2。
窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int res = 0;
        int i = 0;
        unordered_map<int, int>t;
        for (int j = 0; j < fruits.size(); j++) {
            t[fruits[j]]++;
            while (t.size() > 2) {
                auto it = t.find(fruits[i]);
                it->second--;
                if (it->second == 0) t.erase(it);
                i++;
            }
            res = max(res, j - i + 1);
        }
        return res;
    }
};

● 时间复杂度：O(n)。
● 空间复杂度：O(1)。