滑动窗口算法实战：水果成篮与异位词

水果成篮

题目解析

本题要求从一个数组里面选取两个数组成的最长子数组。暴力解法时间复杂度为 O(N^2)，滑动窗口可优化至 O(N)。

算法原理

引入变量判断种类，数的范围是 10 的五次方，所以引入的 hash 表为 100001。固定三部曲：进窗口的时候维护 kinds，如果最开始为 0，那么没有该水果种类，就可以直接 kinds++。判断条件如果 kinds 大于水果种类的话，就出窗口，即 left++。同时要维护 kinds，如果哈希表的映射变为 0 了，那么 kinds 就--。

算法编写

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int hash[100001] = { 0 };
        int ans = 0, kinds = 0;
        for(int left = 0, right = 0; right < fruits.size(); right++) {
            // 进窗口
            if(hash[fruits[right]]++ == 0) kinds++;
            // 判断
            while(kinds > 2) {
                if(--hash[fruits[left++]] == ) kinds--;
            }
            
            ans = (ans, right - left + );
        }
         ans;
    }
};