面试算法大全-滑动窗口总结

短命女 2022-10-06 13:58 230阅读 0赞

## 17、 滑动窗口 ##

#### **滑动窗口算法leetcode经典例题** ####

#### [无重复字符的最长子串][Link 1] ####

滑动窗口

class Solution {
        
        public int lengthOfLongestSubstring(String s) {
        
            if(s.length()==0){
        
                return 0;
            }
            int max=0;
            int start=0;//记录子字符串开始的位置
            HashMap<Character,Integer> map=new HashMap<Character,Integer>();
            for(int end=0;end<s.length();end++){
        
                if(map.containsKey(s.charAt(end))){
        
                    //map.get(s.charAt(end))+1,+1将start移动到重复字符的下一个位置
                    start=Math.max(start,map.get(s.charAt(end))+1);
                }
                //用于存储最近一次重复字符的位置
                map.put(s.charAt(end),end);
                //每移动一次记录max的值
                max=Math.max(max,end-start+1);
            }
            return max;
        }
    }

滑动窗口

class Solution {
        
        public int lengthOfLongestSubstring(String s) {
        
            int n = s.length();
            Set<Character> set = new HashSet<>();
            int res = 0, i = 0, j = 0;
            while(i < n && j < n) {
        
                if(!set.contains(s.charAt(j))) {
        
                    set.add(s.charAt(j++));
                    res = Math.max(res, j - i);
                }else {
        
                    set.remove(s.charAt(i++)); 
                }
            }
            return res;
        }
    }

滑动窗口+Hash+双指针

class Solution {
        
        public int lengthOfLongestSubstring(String s) {
        
            if(s.length()<=1) {
        
                return s.length();
            }
            int result=0;
            //通过哈希表来快速定位重复字符的最新位置
            Map<Character,Integer> map = new HashMap<>();
            
            //用快慢指针，快指针指向最新的下标，慢指针指向不重复的最小下标
            int fast =0;
            int slow =0;
            while(fast<s.length()) {
        
                if(map.containsKey(s.charAt(fast))) {
        
                    slow = Math.max(slow, map.get(s.charAt(fast))+1);
                }
                map.put(s.charAt(fast), fast);
                result = Math.max(result, fast-slow+1);
                fast++;
            }
            return result;
        }
    }

#### [找到字符串中所有字母异位词][Link 2] ####

class Solution {
        
        public List<Integer> findAnagrams(String s, String p) {
        
    
           // 先对目标串p每个字符进行字符计数，统计出每个字符的出现次数
           int pLength = p.length();
           int sLength = s.length();
    
           int[] counts = new int[26];
           for(int i = 0; i < pLength; i++){
        
                counts[p.charAt(i) - 'a']++;
           }
    
           ArrayList<Integer> res = new ArrayList<>();  // 存储结果的结果集
    
            int[] tempCounts = new int[26]; // 记录窗口内每种字符的出现次数
            int left = 0, right = 0;
            while(right < sLength){
        
                int curR = s.charAt(right) - 'a';
                tempCounts[curR]++;        // curR字符的出现次数加一
                right++;    // 新增一个字符后，窗口右指针右移一位
                while(tempCounts[curR] > counts[curR]){
         // 不断缩小窗口大小，直到把超标字符移出去一个，使得不超标
                    tempCounts[s.charAt(left) - 'a']--;
                    left++;     // 移走一个字符后窗口左指针右移一位
                }
                if(right - left == pLength){
        
                    res.add(left);
                }
            }
            return res;
        }
    }

#### [字符串的排列][Link 3] ####

class Solution {
        
        public boolean checkInclusion(String s1, String s2) {
        
            if(s1 == null || s2 == null || s1.length() > s2.length()) return false;
            //滑动窗口 
            HashMap<Character,Integer> needs = new HashMap<>();
            HashMap<Character,Integer> windows = new HashMap<>();
            char[] s1Chars = s1.toCharArray();
            char[] s2Chars = s2.toCharArray();
            for (char item : s1Chars) {
        
                needs.put(item, needs.getOrDefault(item, 0) + 1);
            }
            int len = s2.length();
            int minLen = s1.length();
            int left = 0;
            int right = 0;
            //当前窗口包含的字符数
            int count = 0;
            while(right < len) {
        
                windows.put(s2Chars[right],windows.getOrDefault(s2Chars[right], 0) +  1) ;
                count++;
                // 窗口收缩的条件：当前窗口的字符数量和s1的长度相等
                while(count == minLen ) {
        
                    if (check(needs,windows)){
        
                        return true;
                    }
                    windows.put(s2Chars[left],windows.getOrDefault(s2Chars[left], 0) -  1) ;
                    count--;
                    left++;
                }
                right++;
            }
            return false;
        }
        private boolean check(HashMap<Character,Integer> needs ,HashMap<Character,Integer> windows) {
        
            Iterator<Character> iterator = needs.keySet().iterator();
            while(iterator.hasNext()){
        
                Character c =  iterator.next();
                if (!needs.get(c).equals(windows.get(c))) {
        
                    return false;
                }
            }
            return true;
        }
    }

#### [最小覆盖子串][Link 4] ####

class Solution {
       
        //新建两个Map，needs是存放子串的单个char值和出现的次数；windows是每次滑动的窗口
        Map<Character, Integer> needs = new HashMap<Character, Integer>();
        Map<Character, Integer> windows = new HashMap<Character, Integer>();
    
        public String minWindow(String s, String t) {
            //不符合的情况直接return
            if (s.length() == 0 || t.length() == 0 || s.equals("") || t.equals("") || s.length() < t.length()) return "";
    
            //把子串的数据保存到needs中，即(char, 出现的次数)
            for (int i = 0; i < t.length(); i++) {
                needs.put(t.charAt(i), needs.getOrDefault(t.charAt(i), 0) + 1);
            }
            //窗口左边界，窗口右边界
            int l = 0, r = -1;
            //求最小长度，先置为最大值，最小长度的左边界和右边界
            int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;
            //遍历，窗口往右滑，当窗口右边界的值==字符串长度时结束
            while (r < s.length()) {
                //每次右边界+1
                r++;
                //如果右边界的值是子串的某一值，将窗口windows的所对应的键值对进行+1操作
                if (r < s.length() && needs.containsKey(s.charAt(r))) {
                    windows.put(s.charAt(r),windows.getOrDefault(s.charAt(r), 0) + 1);
                }
                //遍历，右边界右滑已经保证当前窗口已经包含子串，这次是左边界向左移，求最小窗口值
                while (check() && l <= r) {
                    if (r - l + 1 < len) {
                        len = r - l + 1;
                        ansL = l;
                        ansR = l + len;
                    }
                    //如果包含左边界的值，当前窗口对应的键值对进行-1操作，然后求下一个满足要求的滑动窗口
                    if (needs.containsKey(s.charAt(l))) {
                        windows.put(s.charAt(l), windows.getOrDefault(s.charAt(l), 0) - 1);
                    }
                    ++l;
                }
    
            }
            return ansL == -1 ? "" : s.substring(ansL, ansR);
        }
    
        public Boolean check () {
            Iterator iterator = needs.entrySet().iterator();
            while (iterator.hasNext()) {
                Map.Entry entry = (Map.Entry)iterator.next();
                Character character = (Character)entry.getKey();
                Integer integer = (Integer)entry.getValue();
                if (windows.getOrDefault(character, 0) < integer) {
                    return false;
                }
            }
            return true;
        }
    }

#### [连续子数组的最大和][Link 5] ####

class Solution {
        //关键点：滑动窗口和小于等于 0，移动左指针
        public int maxSubArray(int[] nums) {
            //sum 用于记录滑动窗口中所有数的和
            int sum = 0, left = 0, result = Integer.MIN_VALUE;
            for (int right = 0; right < nums.length; right++) {
                sum += nums[right];
                //每次右指针移动一格，就需要比较一次
                result = Math.max(result, sum);
                //注意这里当 left==right 时，left 指针也要移
                while (left <= right && sum <= 0) {
                    sum -= nums[left];
                    left++;
                }
            }
            return result;
        }
    }

#### [长度最小的子数组][Link 6] ####

class Solution {
        public int minSubArrayLen(int s, int[] nums) {
            int n = nums.length;
            if (n == 0) {
                return 0;
            }
            int ans = Integer.MAX_VALUE;
            int start = 0, end = 0;
            int sum = 0;
            while (end < n) {
                sum += nums[end];
                while (sum >= s) {
                    ans = Math.min(ans, end - start + 1);
                    sum -= nums[start];
                    start++;
                }
                end++;
            }
            return ans == Integer.MAX_VALUE ? 0 : ans;
        }
    }

public int minSubArrayLen(int s, int[] nums) {
            int lo = 1, hi = nums.length, min = 0;
            while (lo <= hi) {
                int mid = (lo + hi) >> 1;
                if (windowExist(mid, nums, s)) {
                    hi = mid - 1;//找到就缩小窗口的大小
                    min = mid;//如果找到就记录下来
                } else
                    lo = mid + 1;//没找到就扩大窗口的大小
            }
            return min;
        }
    
        //size窗口的大小
        private boolean windowExist(int size, int[] nums, int s) {
            int sum = 0;
            for (int i = 0; i < nums.length; i++) {
                if (i >= size)
                    sum -= nums[i - size];
                sum += nums[i];
                if (sum >= s)
                    return true;
            }
            return false;
        }

#### [水果成篮][Link 7] ####

class Solution {
        
        public int totalFruit(int[] tree) {
        
            int ans = 0, i = 0;
            Counter count = new Counter();
            for (int j = 0; j < tree.length; ++j) {
        
                count.add(tree[j], 1);
                while (count.size() >= 3) {
        
                    count.add(tree[i], -1);
                    if (count.get(tree[i]) == 0)
                        count.remove(tree[i]);
                    i++;
                }
                ans = Math.max(ans, j - i + 1);
            }
    
            return ans;
        }
    }
    
    class Counter extends HashMap<Integer, Integer> {
        
        public int get(int k) {
        
            return containsKey(k) ? super.get(k) : 0;
        }
    
        public void add(int k, int v) {
        
            put(k, get(k) + v);
        }
    }

#### [滑动窗口的最大值][Link 8] ####

class Solution {
        
        public int[] maxSlidingWindow(int[] nums, int k) {
        
            if(nums.length == 0 || k == 0) return new int[0];
            Deque<Integer> deque = new LinkedList<>();
            int[] res = new int[nums.length - k + 1];
            for(int i = 0; i < k; i++) {
         // 未形成窗口
                while(!deque.isEmpty() && deque.peekLast() < nums[i])
                    deque.removeLast();
                deque.addLast(nums[i]);
            }
            res[0] = deque.peekFirst();
            for(int i = k; i < nums.length; i++) {
         // 形成窗口后
                if(deque.peekFirst() == nums[i - k])
                    deque.removeFirst();
                while(!deque.isEmpty() && deque.peekLast() < nums[i])
                    deque.removeLast();
                deque.addLast(nums[i]);
                res[i - k + 1] = deque.peekFirst();
            }
            return res;
        }
    }

#### [存在重复元素 II][II] ####

class Solution {
        
        public boolean containsNearbyDuplicate(int[] nums, int k) {
        
            int n = nums.length;
            Set<Integer> set = new HashSet<>();
            for( int i = 0; i < n; i ++){
        
                if(set.contains(nums[i]))
                    return true;
                set.add(nums[i]);
                if(set.size() == k + 1)
                    set.remove(nums[i-k]);
            }
            return false;
        }
    }

class Solution {
        
        public boolean containsNearbyDuplicate(int[] nums, int k){
        
    		 
    		 HashSet<Integer> set = new HashSet<>();
    		 for (int i = 0; i < nums.length; i++) {
        
    			if(set.contains(nums[i])) {
        
    				return true;
    			}
    			set.add(nums[i]);
    			if(set.size() == k + 1) {
        
    				set.remove(nums[i-k]);
    			}
    		}
    		 return false;
    	 }
    }

#### [K 个不同整数的子数组][K] ####

class Solution {
        
        public int subarraysWithKDistinct(int[] A, int K) {
        
            Window window1 = new Window();
            Window window2 = new Window();
            int ans = 0, left1 = 0, left2 = 0;
            for (int right = 0; right < A.length; ++right) {
        
                int x = A[right];
                window1.add(x);
                window2.add(x);
                while (window1.different() > K){
        
                    window1.remove(A[left1++]);
                }
                while (window2.different() >= K){
        
                     window2.remove(A[left2++]);
                }
                ans += left2 - left1;
            }
            return ans;
        }
    }
    
    class Window {
        
        Map<Integer, Integer> count;
        int nonzero;
        Window() {
        
            count = new HashMap();
            nonzero = 0;
        }
        void add(int x) {
        
            count.put(x, count.getOrDefault(x, 0) + 1);
            if (count.get(x) == 1)
                nonzero++;
        }
        void remove(int x) {
        
            count.put(x, count.get(x) - 1);
            if (count.get(x) == 0)
                nonzero--;
        }
        int different() {
        
            return nonzero;
        }
    }

#### [替换后的最长重复字符][Link 9] ####

class Solution {
        
        public int characterReplacement(String s, int k) {
        
            //特判
            if (s == null || s.length() == 0){
        
                return 0;
            }
            
            //滑动窗口
            int[] map = new int[26];    //用于统计相连的重复字母个数（每个下标代表一个字母）
            char[] ch = s.toCharArray();
            int maxCount = 0;   //出现过的最长的相连重复字母个数
            //每次循环，right都向右走一步（left和right代表窗口的左右边）
            int left = 0;
            
            for (int right = 0; right < ch.length; right++) {
        
                //从ch数组中取一个字符，添加到数组中的是相连的重复字母个数
                map[ch[right] - 'A']++;
                //比较连续的重复字符个数
                maxCount = Math.max(maxCount, map[ch[right] - 'A']);
                //因为right走了一步，需要判断left是否需要移动，如果left不动，窗口就扩大一格
                //窗口的长度是出现过最长的相连的重复字母个数，窗口的扩增需要保证maxCount+k大（即连续重复字符个数加k超过历史最长）
                if (right - left + 1 > maxCount + k) {
        
                    //进来这里，说明窗口是扩增，left需要和right一起走一步
                    //并且去掉map数组中left字符的数
                    map[ch[left] - 'A']--;
                    left++;
                }
            }
            //数组长度减去left等于窗口的长度，即最长重复字符数
            return ch.length - left;
        }
    }

#### [最长重复子数组][Link 10] ####

public int findLength(int[] A, int[] B) {
        
            if (A.length < B.length)
                return findLengthHelper(A, B);
            return findLengthHelper(B, A);
        }
    
        public int findLengthHelper(int[] A, int[] B) {
        
            int aLength = A.length, bLength = B.length;
            //total是总共运行的次数
            int total = aLength + bLength - 1;
            int max = 0;
            for (int i = 0; i < total; i++) {
        
                //下面一大坨主要判断数组A和数组B比较的起始位置和比较的长度
                int aStart = 0;
                int bStart = 0;
                int len = 0;
                if (i < aLength) {
        
                    aStart = aLength - i - 1;
                    bStart = 0;
                    len = i + 1;
                } else {
        
                    aStart = 0;
                    bStart = i - aLength + 1;
                    len = Math.min(bLength - bStart, aLength);
                }
                int maxlen = maxLength(A, B, aStart, bStart, len);
                max = Math.max(max, maxlen);
            }
            return max;
        }
    
        //计算A和B在上面图中红色框内的最大长度
        public int maxLength(int[] A, int[] B, int aStart, int bStart, int len) {
        
            int max = 0, count = 0;
            for (int i = 0; i < len; i++) {
        
                if (A[aStart + i] == B[bStart + i]) {
        
                    count++;
                    max = Math.max(max, count);
                } else {
        
                    count = 0;
                }
            }
            return max;
        }

[Link 1]: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
[Link 2]: https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/
[Link 3]: https://leetcode-cn.com/problems/permutation-in-string/
[Link 4]: https://leetcode-cn.com/problems/minimum-window-substring/
[Link 5]: https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/
[Link 6]: https://leetcode-cn.com/problems/minimum-size-subarray-sum/
[Link 7]: https://leetcode-cn.com/problems/fruit-into-baskets/
[Link 8]: https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/
[II]: https://leetcode-cn.com/problems/contains-duplicate-ii/
[K]: https://leetcode-cn.com/problems/subarrays-with-k-different-integers/
[Link 9]: https://leetcode-cn.com/problems/longest-repeating-character-replacement/
[Link 10]: https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/