力扣-904题水果成篮（C++）- 滑动窗口

Myth丶恋晨 2022-09-04 03:55 59阅读 0赞

题目链接：[https://leetcode-cn.com/problems/fruit-into-baskets/][https_leetcode-cn.com_problems_fruit-into-baskets]  
题目如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70 1]

class Solution {
        
    public:
        int totalFruit(vector<int>& fruits) {
        
            //抽象出来的模型：
            //求只包含两个不同的数字，且长度最长的子串
            
            //tip:
            //双指针中，用一个指针i来枚举端点，另一个指针是和i相关的，是靠近i最左的且和i之间只有两个元素的位置
    
            int result=0,sublen=0;
            unordered_map<int,int> basket;
    
            for(int i=0,left=0;i<fruits.size();i++){
        
                basket[fruits[i]]++;
                sublen++;
    
                while(basket.size()>2){
        
                    basket[fruits[left]]--;
                    if(basket[fruits[left]]==0) basket.erase(fruits[left]);
                    left++;
                    sublen--;//这是在清零，因为之前的满足条件的最大max已经实时更新到result中了
                }
                
                if(sublen>result) result=sublen;
                
            }
    
            return result;
    
        }
    };

[https_leetcode-cn.com_problems_fruit-into-baskets]: https://leetcode-cn.com/problems/fruit-into-baskets/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]: /images/20220829/62970aee5b3b401aba9515748b4c4476.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70 1]: /images/20220829/27a448c756fd46ef863094d8ee855740.png