leetcode数组、字符串常用方法---滑动窗口

1、固定滑动窗口长度

leetcode438题

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int sLength = s.length(), pLength = p.length();
        if(sLength < pLength)   return new ArrayList<Integer>();
        
        char[] sChars = s.toCharArray(), pChars = p.toCharArray();
        
        int[] hash = new int[26];
        for(int i = 0; i < pLength; ++i)
            hash[pChars[i] - 'a']++;
        
        ArrayList<Integer> result = new ArrayList<Integer>();
        
        int left = 0, right = 0, count = 0;
        for(; right < sLength; ++right){
            hash[sChars[right] - 'a']--;
            if(hash[sChars[right] - 'a'] >= 0)
                count++;
            
            if(right >= pLength){
                if(hash[sChars[left] - 'a'] >= 0)
                    count--;
                hash[sChars[left] - 'a']++;
                left++;
            }
            
            if(count == pLength)
                result.add(left);
        }
        
        return result;
    }
}

分析：通过数组hash来代替使用map，效率更高；滑动窗口的长度固定为目标字符串的长度，即右指针右移一位则左指针跟着右移一位，这样只需要计算当前右指针出遍历的新的字符，中间的字符不用重复计算，下面的方法就是存在重复计算的方法，上面的方法由下面的解法优化而来。

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int sLength = s.length(), pLength = p.length();
        if(sLength < pLength)   return new ArrayList<Integer>();
        
        char[] sChars = s.toCharArray(), pChars = p.toCharArray();
        
        int[] hash = new int[26];
        for(int i = 0; i < pLength; ++i)
            hash[pChars[i] - 'a']++;
        
        ArrayList<Integer> result = new ArrayList<Integer>();
        for(int left = 0; left <= sLength - pLength; left++){
            if(anagramsed(sChars, left, left+pLength-1, hash))
                result.add(left);
        }
        return result;
    }
    private boolean anagramsed(char[] sChars, int left, int right, int[] hash){
        int[] newHash = Arrays.copyOf(hash, 26);
        for(int i = left; i <= right; ++i){
            newHash[sChars[i] - 'a']--;
            if(newHash[sChars[i] - 'a'] < 0)
                return false;
        }
        return true;
    }
}

leetcode567题

分析：注意子串和子序列的区别，子串要求字符是连续的，子序列不要求字符的连续性。字符串a的排列是字符串b的子串，即字符串b是否有一个子串是字符串a的字母异位词，仍然可以用滑动串口来实现，不用set太重了，用一个数组来统计即可。

思路：这个题目和字母异位词的题目十分类似。完全就是一个题，只是换了一种说法而已。

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int length1 = s1.length(), length2 = s2.length();
        if(length1 > length2)   return false;
        
        char[] char1 = s1.toCharArray();
        char[] char2 = s2.toCharArray();
        
        int[] hash = new int[26];
        for(int i = 0; i < length1; ++i)
            hash[char1[i] - 'a']++;
        
        int count = 0;
        for(int left = 0, right = 0; right < length2; right++){
            hash[char2[right] - 'a']--;
            if(hash[char2[right] - 'a'] >= 0)
                count++;
            if(right >= length1){
                hash[char2[left] - 'a']++;
                if(hash[char2[left++] - 'a'] > 0)
                    count--;
            }
            if(count == length1)
                return true;
        }
        return false;
    }
}

leetcode239题

分析：如果采用暴力方法很容易解决，近似平方级别O(NK)的时间复杂度，每次把窗口内的所有值进行遍历，得到窗口内最大的值，然后窗口右移，得到左右的最大值，结果数组的长度等于原数组长度减去k再加1。如何优化时间复杂度呢？采用双端队列的数据结构去保存原数组中元素索引，始终保证当前双端队列中保存的索引是当前滑动窗口中的元素的索引，并且双端队列头上的元素是当前滑动窗口中最大元素的索引。

class Solution {
    //双端队列，两边进行插入或删除操作都是常数时间复杂度
    ArrayDeque<Integer> queue = new ArrayDeque();
    
    //针对当前遍历到的元素清理双端队列
    //窗口每次向右滑动一次，需要将最左边不在窗口中的元素清理出去
    //并将左边比当前元素小的元素全部清理出去
    //由于每次会将左边小的元素清理出去，因此在清理最左边不在窗口中的元素的时候，可能会没有不在窗口中的元素
    private void cleanDeque(int[] nums, int i, int k){
        if(!queue.isEmpty() && queue.getFirst() == i - k)
            queue.removeFirst();
        
        while(!queue.isEmpty() && nums[queue.getLast()] < nums[i])
            queue.removeLast();
    }
    
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        if(len == 0 || k == 0)
            return new int[0];
        if(k == 1)
            return nums;
        
        //遍历前k个元素，针对前k个元素清理双端队列
        //使得双端队列中的第一个元素为前k个元素的最大值
        for(int i = 0; i < k; i++){
            cleanDeque(nums, i, k);
            queue.addLast(i);
        }
        
        int[] result = new int[len - k + 1];
        result[0] = nums[queue.getFirst()];
        
        //遍历剩余元素[k : end] 也就是将窗口进行向右滑动
        //每滑动一位，就对当前元素清理双端队列
        //使得双端队列中始终保持两点
        //1.只有当前窗口中的元素的索引保存在双端队列中
        //2.最左边的元素是当前窗口中最大元素的索引
        for(int i = k; i < len; i++){
            cleanDeque(nums, i, k);
            queue.addLast(i);
            result[i - k + 1] = nums[queue.getFirst()];
        }
        
        return result;
    }
}

2、滑动窗口可以变化

leetcode76题

分析：测试用例中包含大小写字符，因此用作map统计作用的数组需要长一些，ascii码表中大小写及常用字符在第一个字节中，即需要128位的数组来统计大小写字符。

思路：右指针right从头开始向右滑动，count统计当前子串中和目标字符串匹配上字符的数量，一旦找到一个包含目标字符串所有字符的子串，则让left开始向右滑动，直到当前子串[left, right]中不再包含目标字符串所有字符，则停止left向右滑动，继续right向右滑动，继续right滑动找到包含目标字符串所有字符的子串，重复上述步骤直至right到达结尾

class Solution {
    public String minWindow(String s, String t) {
        int sLength = s.length(), tLength = t.length();
        if(sLength < tLength)   return "";
        
        char[] sChars = s.toCharArray(), tChars = t.toCharArray();
        String result = "";
        int resultLength = sLength;
        
        int[] hash = new int[128];
        for(int i = 0; i < tLength; i++)
            hash[tChars[i]]++;
        
        int left = 0, right = 0, count = 0;
        for(; right < sLength; right++){
            hash[sChars[right]]--;
            if(hash[sChars[right]] >= 0)
                count++;
            if(count == tLength){
                while(count == tLength){
                    if(resultLength >= right - left + 1){
                        resultLength = right - left + 1;
                        result = s.substring(left, right + 1);
                    }
                    
                    if(hash[sChars[left]] >= 0)
                        count--;
                    hash[sChars[left]]++;
                    
                    left++;
                }
            }
            
        }
        
        return result;
    }
}

leetcode3题

分析：要找到无重复字符的最长子串，通过滑动窗口的方式，[left, right]表示当前窗口，right不断向右滑动扩展子串范围(只要当前子串无重复字符就继续向右滑动)，出现重复字符后，right停止向右滑动，left开始向右滑动，直到当前子串中不再包含重复字符，然后重复right向右滑动的过程。在right向右滑动的同时去更新结果变量，使其值为最长无重复子串的长度。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int length = s.length();
        if(length == 0) return 0;
        
        int result = 0;
        char[] chars = s.toCharArray();
        Set<Character> set = new HashSet<>();
        for(int left = 0, right = 0; right < length;){
            if(!set.contains(chars[right])){
                set.add(chars[right++]);
                result = Math.max(result, right - left);
            }else{
                set.remove(chars[left++]);
            }
        }
        return result;
    }
}

leetcode992题

分析：题目要求找到该数组的一个子数组，子数组的不同数值的个数count为K，首先想到使用滑动窗口，但是刚开始把问题简单化了，认为只要右指针不断扩展，当前滑动窗口的不同数值个数为k时就得到一个子数组，当不同数值个数count大于k时再让左指针右移即可，而且采用HashSet去重来统计当前窗口中不同数值的个数。

这个思路存在两个问题，第一：当前滑动窗口中的不同数值个数count大于k时让左指针右移会导致丢失部分结果，例如 A = [1,2,1,2,3], K = 2 这个例子，假如右指针移到 index 为 3 的位置，如果按之前的思路左指针根据 count 来移动，当前窗口是 [1,2,1,2]，但是怎么把 [2,1] 给考虑进去呢？也就是这个思路会把当前窗口的一些满足条件的子窗口忽略掉，而这些子窗口可能是满足条件的子数组。第二：通过HashSet去重来统计count会导致丢失部分结果，因为题目要求子数组不必独立，所以利用HashSet去重会使得中间重复数值被忽略，而这些重复数值可能会组成新的子数组。

那如何将中间结果考虑进去防止结果丢失呢？对上述思路进行改进，首先不再使用HashSet来统计，而是使用hash数组来统计，而且题目条件告诉我们 1 <= A[i] <= A.length 这就是告诉我们用hash数组啊。数组设置为A.length+1长度。A中数值作为对hash数组的索引，然后hash数组的值代表对应A中数值的个数。其次，不能简单的让左指针右移，看下面的分析。当窗口中不同数值个数小于k时，只需让右指针右移，并更新统计量；当窗口中不同数值个数等于k时，情况分析如下图，每次新增一个元素，有两种情况：1.不同数值个数仍然是k，此时满足条件的子数组数量会增加（上次增量+1）；2.不同数值个数大于k，则需要移动左指针使得个数小于k，且增量回到1（初试增量）.

k = 2
[1,2,1,2,3]  // 窗口满足条件
 l r         // 满足条件的子数组 [1,2]
 
[1,2,1,2,3]  // 窗口满足条件
 l   r       // 满足条件的子数组 [1,2],[2,1],[1,2,1]
 
[1,2,1,2,3]  // 窗口满足条件
 l     r     // 满足条件的子数组 [1,2],[2,1],[1,2,1],[1,2],[2,1,2],[1,2,1,2]

[1,2,1,2,3]  // 窗口不满足条件，移动左指针至满足条件
 l       r   

[1,2,1,2,3]  // 窗口满足条件
       l r   // 满足条件的子数组 [1,2],[2,1],[1,2,1],[1,2],[2,1,2],[1,2,1,2],[2,3]

class Solution {
    public int subarraysWithKDistinct(int[] A, int K) {
        int length = A.length;
        int[] hash = new int[length + 1];

        int l = 0, results = 0, count = 0, result = 1;
        for (int r = 0; r < length; ++r) {
            hash[A[r]]++;

            if (hash[A[r]] == 1) {
                count++;
            }

            while (hash[A[l]] > 1 || count > K) {
                if (count > K) {
                    result = 1;
                    count--;
                } else {
                    result++;
                }
                hash[A[l]]--;
                l++;
            }

            if (count == K) {
                results += result;
            }
        }

        return results;
    }
}

leetcode159题

分析：首先这个题是最长子串，而不是子序列，子串是连续的字符组成的，子序列不必连续。至多包含两个不同的子串，即全是相同的字符组成的子串、两个不同的字符组成的子串，如果不同字符的个数大于等于3，就不符合题意了要得到最长的子串，可以考虑滑动窗口，因为要统计不同字符的种类个数，需要计数，这里考虑可以用map（不能用set因为set会忽略相同字符的数量而只保留一个）进行计数，窗口内的就是目前的最长子串，遍历一遍字符串，得到最长的子串。然后现在再思考左右指针该如何移动，以及何时移动？如果当前窗口中的子串符合至多两个的条件，则右指针右移一位；如果当前窗口中的子串不符合条件，则考虑左指针向右移动一位，移动的同时需要将计数map中该字符减一，如果减一后为零，直接删除该字符在map中的记录，这样窗口中的字符种类数量又符合条件，右指针可以继续右移，直到到达字符串的结尾。

class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        int len = s.length();
        if(len <= 2)
            return len;
        char[] chars = s.toCharArray();
        Map<Character, Integer> map = new HashMap<>();
        int left = 0, right = 0, result = 0;
        while(right < len && left < len){
            if(map.containsKey(chars[right])){
                map.put(chars[right], map.get(chars[right])+1);
                right++;
            }else{
                map.put(chars[right], 1);
                right++;
            }
            
            if(map.size() <= 2){
                result = Math.max(result, right - left);
            }else{
                while(map.size() >= 3){
                    if(map.get(chars[left]) > 1){
                        map.put(chars[left], map.get(chars[left]) - 1);
                        left++;
                    }else{
                        map.remove(chars[left]);
                        left++;
                    }
                }
            }
        }
        return result;
    }
}

leetcode340题

分析：这个题和上面的159题一本一样，只不过159是特殊化的340，159要求至多2个，340要求至多k个。

class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        int len = s.length();
        if(len <= k)
            return len;
        
        char[] chars = s.toCharArray();
        Map<Character, Integer> map = new HashMap<>();
        int left = 0, right = 0, result = 0;
        while(right < len && left < len){
            if(map.containsKey(chars[right])){
                map.put(chars[right], map.get(chars[right]) + 1);
                right++;
            }else{
                map.put(chars[right], 1);
                right++;
            }
            
            if(map.size() <= k){
                result = Math.max(result, right - left);
            }else{
                while(map.size() > k){
                    if(map.get(chars[left]) > 1){
                        map.put(chars[left], map.get(chars[left]) - 1);
                        left++;
                    }else{
                        map.remove(chars[left]);
                        left++;
                    }
                }
            }
        }
        return result;
    }
}