滑动窗口经典问题

关卡名	滑动窗口高频问题	我会了??
内容	1.掌握最长子串问题	??
	2.理解长度最小的子数组问题	??
	3.掌握盛水最多的容器问题	??
	4.理解异位词问题如何解决	??

1 最长子串专题?

先来看一道高频算法题：无重复字符的最长子串。具体要求是给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。例如，输入: s = "abcabcbb" 则输出3，因为无重复字符的最长子串是 "abc"，所以其长度为3。
怎么做后面再说，如果再变一下要求，至多包含两个不同字符的最长子串，该怎么做呢？
再变一下要求，至多包含 K 个不同字符的最长子串，该怎么做呢？
到这里是否感觉，这不在造题吗？是的！上面就分别是LeetCode3、159、340题，而且这几道题都可以用滑动窗口来解决。学会之后，我们就总结出滑动窗口的解题模板了。
接下来，我们就一道一道看。

1.1 无重复字符的最长子串?

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

输入: s = "abcabcbb"

输出: 3

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

要找最长子串，必然要知道无重复字符串的首和尾，然后再从中确定最长的那个，因此至少两个指针才可以，这就想到了滑动窗口思想。即使使用滑动窗口，深入分析会发现具体处理起来有多种方式。这里介绍一种经典的使用Map的思路。
我们定义一个K-V形式的map，key表示的是当前正在访问的字符串，value是其下标索引值。我们每访问一个新元素，都将其下标更新成对应的索引值。具体过程如下图：

如果是已经出现过的，例如上述示例中的 abcabc，当第二次遇到a时，我们就更新left成为第一个b所在的位置，此时惊奇的发现left要移动的位置恰好就是map.get(’a‘) + 1=1，我们将'a'用序列来表示，放在一起就是map.get(s.charAt(i)) + 1。其他情况可以参考图示依次类推。
有一种特殊情况我们需要考虑，例如abba，我们第二次访问b时，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.charAt(right)) + 1);
            }
            map.put(s.charAt(right), right);
            max = Math.max(max, right - left + 1);
        }
        return max;
}

除了上述方法，不用Hash存储索引，也可以用滑动窗口思想来解决，感兴趣的可以研究一下。

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

给定一个字符串 s ，找出 至多 包含两个不同字符的最长子串 t ，并返回该子串的长度，这就是LeetCode159题。例如：

输入: "eceba"

输出: 3

解释: t 是 "ece"，长度为3。

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

?

我们接下来需要解决两个问题，一个是怎么判断只有2个元素，另一个是移除的时候怎么知道移除谁，以及移除之后left是什么。
要判断只有2个元素，还是Hash好用，每一个时刻，这个 hashmap 包括不超过 3 个元素。这里还要考虑到要移除谁，所以我们要设计一下Hash的Key-Value的含义。我们把字符串里的字符都当做键，在窗口中的最右边的字符位置作为值。此时使用下面的代码就可以确定要删除谁，以及窗口left的新位置：

伪码，从Hash中找最小值

del_idx = Collections.min(hashmap.values());

left = del_idx + 1;

为什么呢？我们还是画图看一下：

所以我们可以充分利用Map的工具来解决该问题：

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++);

            // 如果大小达到了3个
            if (hashmap.size() == 3) {
                // 最左侧要删除的位置
                int del_idx = Collections.min(hashmap.values());
                hashmap.remove(s.charAt(del_idx));
                // 窗口left的新位置
                left = del_idx + 1;
            }

            maxLen = Math.max(maxLen, right - left);
        }
        return maxLen;
    }

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

如果再提高一下难度， 至多包含 K 个不同字符的最长子串该怎么办呢？这就是LeetCode340题。
题目的完整要求是：给定一个字符串 s，找出 至多 包含 k 个不同字符的最长子串T。示例：

输入: s = "eceba", k = 2

输出: 3

解释: 则 T 为 "ece"，所以长度为 3。

本题与上面的题几乎没有区别，只要将判断hash大小为2改成k就可以，超过2就是k+1。十分钟实现：

public  int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (s.length() < k + 1) {
            return s.length();
        }
        int left = 0, right = 0;
        HashMap<Character, Integer> hashmap = new HashMap<>();
        int maxLen = k;
        while (right < s.length()) {
            if (hashmap.size() < k + 1)
                hashmap.put(s.charAt(right), right++);
            // 如果大小达到了k个
            if (hashmap.size() == k + 1) {
                int del_idx = Collections.min(hashmap.values());
                hashmap.remove(s.charAt(del_idx));
                // 窗口left的新位置
                left = del_idx + 1;
            }
            maxLen = Math.max(maxLen, right - left);
        }
        return maxLen;
    }

2 长度最小的子数组?

LeetCode209.长度最小的子数组,给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

输入：target = 7, nums = [2,3,1,2,4,3]

输出：2

解释：子数组 [4,3] 是该条件下的长度最小的子数组。

?本题可以使用双指针来解决，也可以视为队列法，基本思路是先让元素不断入队，当入队元素和等于target时就记录一下此时队列的容量，如果队列元素之和大于target则开始出队， 直到小于target则再入队。
如果出现等于target的情况，则记录一下此时队列的大小，之后继续先入队再出队。每当出现元素之和等于target时我们就保留容量最小的那个。
实现代码如下：

public int minSubArrayLen(int target, int[] nums) {
        int left = 0, right = 0, sum = 0, min = Integer.MAX_VALUE;
        while (right < nums.length) {
            sum += nums[right++];
            while (sum >= target) {
                min = Math.min(min, right - left);
                sum -= nums[left++];
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }

3. 盛水最多的容器?

LeetCode11.给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。

示例：

输入：[1,8,6,2,5,4,8,3,7]

输出：49

解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

本题看似复杂，但其实简单的很。设两指针 i , j ，指向的水槽板高度分别为 h[i] , h[j] ，此状态下水槽面积为S(i,j) 。由于可容纳水的高度由两板中的 短板 决定，因此可得如下面积公式 ：
S(i,j)=min(h[i],h[j])×(j?i)
在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽底边宽度?1 变短：

• 若向内移动短板 ，水槽的短板min(h[i],h[j]) 可能变大，因此下个水槽的面积可能增大 。
• 若向内移动长板 ，水槽的短板min(h[i],h[j]) 不变或变小，因此下个水槽的面积一定变小 。

因此，只要初始化双指针分列水槽左右两端，循环每轮将短板向内移动一格，并更新面积最大值，直到两指针相遇时跳出；即可获得最大面积。?

public int maxArea(int[] height) {
    int i = 0, j = height.length - 1, res = 0;
    while(i < j) {
        res = height[i] < height[j] ? 
              Math.max(res, (j - i) * height[i++]): 
              Math.max(res, (j - i) * height[j--]); 
    }
    return res;
}

4 寻找子串异位词（排列）?

如果两个字符串仅仅是字母出现的位置不一样，则称两者相互为对方的一个排列，也称为异位词。
如果判断两个字符串是否互为排列，是字符串的一个基本算法。现在我们给增加难度。看LeetCode567和438两个题。

4.1 字符串的排列

LeetCode567.给你两个字符串s1和s2 ，写一个函数来判断 s2是否包含 s1的排列。如果是，返回 true ；否则，返回 false 。换句话说，s1 的排列之一是 s2 的子串 。其中s1和s2都只包含小写字母。

示例：

输入：s1 = "ab" s2 = "eidbaooo"

输出：true

解释：s2 包含 s1 的排列之一 ("ba").

本题因为字符串s1的异位词长度一定是和s2字符串的长度一样的，所以很自然的想到可以以s1.length()为大小截图一个固定窗口，然后窗口一边向右移动，一边比较就行了。此时可以将窗口内的元素和s1先做一个排序，然后再比较即可，但是这样做的问题是排序代价太高了，我们需要考虑性能更优的方法。
所谓的异位词不过两点：字母类型一样，每个字母出现的个数也是一样的。题目说s1和s2都仅限小写字母，因此我们可以创建一个大小为26的数组，每个位置就存储从a到z的个数，为了方便操作，索引我们使用
index=s1.charAt(i) - 'a'
来表示，这是处理字符串的常用技巧。
此时窗口的right向右移动就是执行：
charArray2[s2.charAt(right) - 'a']++;
而left向右移动就是执行：

伪码：

int left = right - sLen1;

charArray2[s2.charAt(left) - 'a']--;

所以，完整代码如下：

public boolean checkInclusion(String s1, String s2) {
    int sLen1 = s1.length(), sLen2 = s2.length();
    if (sLen1 > sLen2) {
        return false;
    }
    int[] charArray1 = new int[26];
    int[] charArray2 = new int[26];
    for(int i=0;i<sLen1;i++){
        ++charArray1[s1.charAt[i]-'a'];
        ++charArray2[s2.charAt[i]-'a'];
    }
    if (Arrays.equals(charArray1, charArray2)) {
            return true;
    }
    for(int right=sLen1;right<sLen2;right++){
        charArray2[s2.charAt(right)-'a']++;
        int left=right-sLen2;
        charArray2[s2.charAt(left)-'a']--;
        if (Arrays.equals(charArray1, charArray2)) {
                return true;
        }
    }
    return false;
}

?上面只是判断有没有，那如果让你确定一下有几个呢？有或者如果有的话，将异位词的开始位置输出出来怎么做呢？这就是LeetCode438题。

4.2 找到字符串中所有字母异位

LeetCode438.找到字符串中所有字母异位词，给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。注意s和p仅包含小写字母。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。例如：

输入: s = "cbaebabacd", p = "abc"

输出: [0,6]

解释:

起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。

起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

本题的思路和实现与上面几乎一模一样，唯一不同的是需要用一个List，如果出现异位词，还要记录其开始位置，那直接将其add到list中就可以了。完整代码：

public List<Integer> findAnagrams(String s, String p) {
       int sLen = s.length(), pLen = p.length();
        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }
        List<Integer> ans = new ArrayList<Integer>();
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        //先分别初始化两个数组
        for (int i = 0; i < pLen; i++) {
            sCount[s.charAt(i) - 'a']++;
            pCount[p.charAt(i) - 'a']++;
        }
        if (Arrays.equals(sCount, pCount)) {
            ans.add(0);
        }

        for (int left = 0; left < sLen - pLen; left++) {
            sCount[s.charAt(left) - 'a']--;
            int right=left + pLen;
            sCount[s.charAt(right) - 'a']++;

            if (Arrays.equals(sCount, pCount)) {
            //上面left多减了一次，所以
                ans.add(left + 1);
            }
        }
        return ans;
}

?

?