算法通关村第十六关—滑动窗口经典问题(白银)

??滑动窗口经典问题

一、最长子串专题

1.1 无重复字符的最长子串

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

输入：s="abcabcbb"
输出：3
解释：因为无重复字符的最长子串是"abc"，所以其长度为3。

?要找最长子串，必然要知道无重复字符串的首和尾，然后再从中确定最长的那个，因此至少两个指针才可以，这就想到了滑动窗口思想。
?定义一个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后退了，显然不对。
?我们应该让t在2的基础上继续向前，那该怎么办呢？和原来的对比一下，将最大的加1就可以了，也就是：left=Math.max(left,map.get(s.charAt(i))+1);
完整的代码如下：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(),max = 0; 
        Map<Character, Integer> map = new HashMap<>(); 
        for(int end = 0, start = 0; end < n; end++){ 
            char element = s.charAt(end); 
            if(map.containsKey(element)){ 
                start = Math.max(map.get(element)+1, start);
            }
            max = Math.max(max, end - start + 1);  
            map.put(element, end);  
        }
        return max;
    }
}

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

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

输入："eceba"
输出：3
解释：t是"ece",长度为3。

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

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

//伪码，从Hash中找最小值
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++);
    //如果大小达到了3个
    if(hashmap.size()==3){
        //最左侧要删除的位置
        int del_idx = Collections.min(hashmap.values());
        hashmap.remove(s.charAt(delidx));
        //窗口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 lengthofLongestSubstringTwoDistinct(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+1个
    if(hashmap.size()== k + 1){
        //最左侧要删除的位置
        int del_idx = Collections.min(hashmap.values());
        hashmap.remove(s.charAt(delidx));
        //窗口left的新位置
        left = del_idx + 1;
    }
    maxLen = Math.max(maxLen, right -left);
}
return maxLen;
}

二、长度最小的子数组

?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时我们就保留容量最小的那个。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0, right = 0;
        int sum = 0;
        int min = nums.length + 1;
        for(right = 0; right < nums.length; right++){
            sum+= nums[right];
            if(sum >= target){
                for(;left < right; left++){
                    if(sum - nums[left]>= target) sum -= nums[left];
                    else break;
                }
                min = Math.min(min, right - left + 1);
            }
        }
        
        return min == nums.length + 1? 0 : min;
    }
}

三.盛水最多的容器

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

平平无奇双指针，下面自己的解法

class Solution {
    public int maxArea(int[] height) {
        int left = 0,right = height.length-1; //创建左右指针，分别指向数组的开端和末端
        int max = 0; //max用于记录最大值
        while(left < right){ //当左右指针还未重合时
            int v = (right - left) * Math.min(height[left] , height[right]); //计算当前的容水量
            max = max > v ? max : v; //利用三目运算符判断最大值是否需要改变
            if(height[left] < height[right]) left++;  //对指向 高度比较低 的指针进行移动
            else right--;
        }
        return max; //返回最大值
    }
}

讲义解法,压缩版

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.1 字符串的排列

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

示例：
输入：s1="ab"s2="eidba00o"
输出：true
解释：s2包含s1的排列之一("ba").

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

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

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

输入：s="cbaebabacd",p="abc"
输出：[0,6]
解释：
起始索引等于0的子串是
"cba",它是"abc"的异位词。
起始索引等于6的子串是"bac",它是"abc"的异位词。

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

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList();
        if(s.length() < p.length()) return list;
        int[] arr1 = new int[26]; //保存p
        int[] arr2 = new int[26]; //保存s
        for(int i = 0; i < p.length(); i++){
            arr1[p.charAt(i) - 'a']++;
            arr2[s.charAt(i) - 'a']++;
        }
        if(Arrays.equals(arr1,arr2)) list.add(0);
        int left = 0;
        for(int right = p.length(); right < s.length(); right++){
            arr2[s.charAt(right) - 'a']++;
            arr2[s.charAt(left) - 'a']--;
            left++;
            if(Arrays.equals(arr1,arr2)) list.add(left);
        }
        return list;
    }
}