算法通关村——滑动窗口高频问题

滑动窗口之最长子串

无重复字符的最长子串

LeetCode3. 给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。

示例：

输入：s = “abcabcbb”

输出：3

解释：因为无重复字符的最长子串是"abc"，所以其长度为3.

要找最长子串，必然要知道无重复字符串的首和尾，然后再从中确定最长的那个，因此至少两个指针才可以，这就想到了滑动窗口思想。这里介绍一种经典的使用Map的思路。

定义一个K-V形式的map，key表示的是当前正在访问的字符串，vaule是其下标索引值。我们每访问一个新元素，都将其下标更新成对应的索引值。具体过程如下图：

如果是已经出现过的，例如上述示例中的abcabc，当第二次遇到a时，我们就更新left成为第一个b所在的位置，此时可以发现left要移动的位置恰好就是map.get(‘a’) + 1 = 1，将’a’用序列表示，放在一起就是map.get(s.charAt(i)) + 1。其他情况参考图示以此类推。

这里需要考虑一种特殊情况，例如abba，第二次访问b时，更新left，left=map.get(‘b’) + 1 =2

然后继续访问第二个a，此时left=map.get(‘a’)+1=1,也就是left后退了，显然不对。

应该让left在2的基础上继续向前，我们可以和原来的对比一下，将最大的加1就可以了，也就是left=Math.max(left, map.get(s.charAt(i))+1)

完整代码如下：

public int lengthOfLongestSubstring(String s) {
    if (s.length() == 0) return 0;
    HashMap<Character, Integer> map = new HashMap<Character, Integer>();
    int max = 0;
    int left = 0;
    for (int right = 0; right < s.length(); right++) {
        if (map.containsKey(s.charAt(right))) {
            left = Math.max(left, map.get(s.chatAt(right)) + 1);
        }
        map.put(s.charAt(right), right);
        max = Math.max(max, right - left + 1);
    }
    return max;
}

至多包含两个不同字符的最长子串

LeetCode159. 给定一个字符串，找出至多包含两个不同字符的最长子串t，并返回该子串的长度。

示例：

输入：“eceba”

输出：3

解释：t 是"ece"，长度为3.

我们仍然使用left和right来锁定一个窗口，然后一边向右移动一边分析。我们用aabbcccd这个序列来看

对于这个题，有两个问题需要解决，一个是怎么判断只有2个元素，另一个是移除的时候怎么知道移除谁，以及移除之后left是什么。

要判断只有2个元素，还是Hash好用，每一个时刻，这个Hashmap包括不超过3个元素。

这里还要考虑到要移除谁，所以我们要设计一下Hash的K-V含义。我们把字符串里的字符都当作键，在窗口中的最右边的字符位置作为值。此时使用下面的代码可以确定删除谁，以及窗口left的新位置：

del_idx = Collections,min(hashmap.values());
left = del_idx + 1;

完整代码如下：

public int lengthOfLongestSubstringTwoDistinct(String s) {
    if(s.length() < 3) {
        return s.length();
    }
    int left = 0, right = 0;
    HashMap<Character, Integer> hashmap = new HashMap<>();
    int maxLen = 2;
    
    while (right < s.length()) {
        if (hashmap.size() < 3) {
            hashmap.put(s.charAt(right), right + 1);
        }
        
        //如果大小达到了3
        if (hashmap.size() == 3) {
            //最左侧要删除的位置
            int delIndex = Collection.min(hashmap.values());
            hashmap.remove(s.charAt(delIndex));
            //窗口left的新位置
            left = delIndex + 1;
        }
        
        maxLen = Math.max(maxLen, right - left);
    }
    return maxLen;
}

如果是至多包含k个不同字符的最长子串，只用将判断hash大小为2改成k就可以了，超过2就是k+1即可。