【滑动窗口】水果成篮

904. 水果成篮 - 力扣（LeetCode）

题目解析：

题目要求：

在数组中找出一个最长连续子数组，该子数组最多只能包含两种不同的元素。

暴力解法思路：

从数组的第一个元素开始，依次向后遍历：

1. 当遇到的元素种类超过两种时，终止当前遍历
2. 每个元素遍历完成后，更新最大子数组长度记录

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int max_len = 0;
        int n = fruits.size();
        // 遍历所有可能的起始位置
        for (int start = 0; start < n; start++) {
            unordered_set<int> basket; // 用集合存当前篮子里的水果类型（最多2种）
            int current_len = 0;
            // 从start开始，向后连续收集水果
            for (int end = start; end < n; end++) {
                basket.insert(fruits[end]);
                // 若篮子里的类型超过2种，停止当前起始位置的收集
                if (basket.size() > 2) {
                    break;
                }
                current_len++; // 收集当前水果，长度+1
            }
            // 更新最大长度
            max_len = max(max_len, current_len);
        }
        return max_len;
    }
};

通过测试用例，提交超时：

时间复杂度为:O(N^2)

优化：

暴力解法中的冗余操作分析：

以起点0（第一个3）为例：遍历到位置4（水果2）时，篮子里已包含3、1、2三种水果，此时停止遍历，有效长度为4（对应子数组[3,3,3,1]）。

随后暴力解法会从起点1（第二个3）和起点2（第三个3）重新开始遍历。但这两个起点的初始水果都是3，与起点0的核心组合（3和1）完全一致，因此其遍历结果必然比起点0更短，属于可跳过的无效计算。

fruits = [3,3,3,1,2,1,1,2,3,3,4]

优化无效起点的处理（避免重复遍历第二个/第三个3） 从起点0遍历至right=4（水果2）时发现非法情况，最后合法位置为fruits[3]=1

定位新起点步骤：

1. 从位置3向前查找1的最左位置，确定new_start=2
2. 设置新起点start=3（跳过位置1和2的两个3），完美匹配"直接从1开始"的逻辑

优化遍历策略：

1. 右指针无需回退，从位置4（水果2）继续扩展窗口
2. 新组合必然包含右边界前一个水果（1）和当前右指针水果（2），形成{1,2}组合，验证了"新组合必含右边界数"的观察

暴力解法优化：

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int max_len = 0;
        int n = fruits.size();
        int start = 0; // 起始位置，不再逐个+1，而是跳转到有效起点
        
        while (start < n) {
            unordered_set<int> basket; // 存储当前组合的两种水果
            int right = start; // 右指针不回退，从start开始（但后续会复用前序遍历的位置）
            int current_len = 0;
            
            // 遍历右指针，直到出现第3种水果
            while (right < n) {
                basket.insert(fruits[right]);
                if (basket.size() > 2) break;
                current_len++;
                right++;
            }
            
            // 更新最大长度
            max_len = max(max_len, current_len);
            
            // 核心优化：跳过无效起点，直接跳到新组合的起点
            if (right >= n) break; // 右指针到末尾，无需继续
            
            // 新组合必然包含右边界的水果（fruits[right-1]），找到该水果的最左位置作为新start
            int last_fruit = fruits[right-1]; // 最后一个合法水果（右边界前一个）
            // 从right-1向前找，直到不是last_fruit，下一个位置就是新start
            int new_start = right - 1;
            while (new_start >= start && fruits[new_start] == last_fruit) {
                new_start--;
            }
            start = new_start + 1; // 跳到新组合的起点（避免重复1、3组合）
        }
        
        return max_len;
    }
};

通过全部用例，提交通过：

再优化（滑动窗口）：

该解法需要手动跳过无效元素且包含两层嵌套循环，时间复杂度仍为O(N²)。

借鉴上面的优化思路：

1. 跳过无需遍历的元素
2. 避免右边界回退

优化循环结构，采用滑动窗口机制。通过动态调整窗口边界并维护内部元素，将原本嵌套的双循环合并为单次遍历，提升执行效率。

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int left = 0;
        int right = 0;
        int len = 0;
        int count=0;
        unordered_map<int, int> hash;
        
        while (right < fruits.size())
        {
            // 1. 加入右边界水果（新组合必含右边界数）
            hash[fruits[right]]++;
            if (hash[fruits[right]] == 1) {
                count++;
            }
            
            // 2. 合法窗口更新长度
            if (count <= 2) {
                len = len > (right - left + 1) ? len : right - left + 1;
            }
            
            // 3. 自动跳过无效起点（替代手动找new_start）
            while (count > 2) {
                hash[fruits[left]]--;
                if (hash[fruits[left]] == 0)
                    count--;
                left++; // left跳到新起点，无需遍历中间无效位置
            }
            
            // 4. 右指针不回退
            right++;
        }
        return len;
    }
};

注意：更新窗口最大长度前，需确保count值已更新，以此作为最新判断依据。

通过全部用例，提交通过：

时间复杂度为：O（N）