Subarray + sliding window类型总结

SubString + Sliding window 类题型
借用Map的解法

第一类：找尽量不重复的最大substring /substring个数

3. Longest Substring Without Repeating Characters
常见是Set的解法，Discussion里面有说就不写在这里了。

Map方法：一旦map中有当前char且比慢指针 i 更后面就要更新慢指针 i
代码如下：
public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) return 0;
        int result = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0, j = 0; j < s.length(); j++) {
            char c = s.charAt(j);
            if (map.containsKey(c) && map.get(c) >= i) {
                i = map.get(c);
                i++;
            }
            result = Math.max(result, j - i + 1);
            map.put(c, j);
        }
        return result;
     }


第二类：找尽量重复的最大substring/substring个数

159. Longest Substring with At Most Two Distinct Characters
340. Longest Substring with At Most K Distinct Characters
992. Subarrays with K Different Integers

这三题可以用同一个模版解，模版是340题答案，最多K个不同字符的最大subarray长度。
其中992题虽然问的是正好K个不同字符，但实际只要用（最多K个 - 最多K-1个）就可以了，也就是return 模版(A, K) - 模版(A, K - 1);这里只要改input类型。

如果是要求substring个数（992），只需要把res = Math.max(res, i - start + 1)更改为res += j - i + 1就可以了。

模版如下：
public int lengthOfLongestSubstringKDistinct(String s, int k) {        if (s == null || s.length() == 0) return 0;
        HashMap<Character, Integer> map = new HashMap<>();
        int start = 0;
        int res = 0;
        for(int i = 0; i < s.length(); i++) {
            map.put(s.charAt(i), i);
            if (map.size() > k) {
                int leftMost = s.length();
                for (int num : map.values()) {
                    leftMost = Math.min(leftMost, num);
                }
                map.remove(s.charAt(leftMost));
                start = leftMost + 1;
            } else {
                res = Math.max(res, i - start + 1);
            }
        }
        return res;
    }

每次移除尽可能短的字符，使得剩下的subarray (i 到 j) 字符数目不超过K
我觉得这种模版其实类似固定大小为K的最小堆 min priority heap, 只不过元素是map, 每次加入新元素后，如果map size大于K了，就pop出一个value最小的map.

补充：
用Array会比Map快，但需要限定是ASCII。
模版的Set方法如下：
public int lengthOfLongestSubstringKDistinct2(String s, int k) {        int[] count = new int[256];
        int res = 0, num = 0, j = 0;
        for (int i = 0; i < s.length(); i++) {
            if (count[s.charAt(i)] == 0) num++;
            count[s.charAt(i)]++;
            while (num > k) {
                count[s.charAt(j)]--;
                if (count[s.charAt(j)] == 0) num--;
                j++;
            }
            res = Math.max(res, i - j + 1);
        }
        return res;
    }