窗口滑动算法

窗口滑动算法
强烈推介IDEA2020.2破解激活,IntelliJ IDEA 注册码,2020.2 IDEA 激活码

1.求无重复字符的最长子串

LeetCode题目 3. 无重复字符的最长子串

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

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
    请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

1.1 思路分析

这道题主要用到思路是:滑动窗口。

那么什么是滑动窗口?

窗口滑动其实就是一个队列,比如例题中的 abcabcbb,进入这个队列(窗口)为 abc 满足题目要求,当再进入 a,队列变成了 abca,这时候不满足要求。所以,我们要移动这个队列!

但是如何移动呢?

我们只要把队列的左边的元素移出就行了,直到满足题目要求!一直维持这样的队列,找出队列出现最长的长度时候,求出解!

时间复杂度:O(n)O(n) ,参考来自:滑动窗口

1.2 算法实现

class Solution {
   
    public int lengthOfLongestSubstring(String s) {
   
        if (s.length()==0){
   
            return 0;
        }
        //left记录窗口左边界
        int max = 0, left = 0;
        Map<Character,Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
   
            //窗口新增元素
            char ch = s.charAt(i);
            //窗口中已经包含新增元素,则更新left
            if (map.containsKey(ch)){
   
                left = Math.max(left,map.get(ch)+1);
            }
            map.put(s.charAt(i),i);
            //计算窗口长度 i-left+1,并更新最大窗口长度
            max = Math.max(max,i-left+1);
        }
        return max;
    }
}

2.求最小覆盖子串

该题依旧适用窗口滑动,题目源自LeetCode 76. 最小覆盖子串

给你一个字符串 S、一个字符串 T 。请你设计一种算法,可以在 O(n) 的时间复杂度内,从字符串 S 里面找出:包含 T 所有字符的最小子串。
示例:

输入:S = "ADOBECODEBANC", T = "ABC"
输出:"BANC"

提示:

  • 如果 S 中不存这样的子串,则返回空字符串 “”。
  • 如果 S 中存在这样的子串,我们保证它是唯一的答案。

上文已经有过一次滑动窗口的简单实用,该题增加了难度和复杂度,参考代码实现如下:

public class Solution {
   

    public static void main(String[] args) {
   
        Solution solution = new Solution();
        System.out.println(solution.minWindow("ADOBECODEBANC","ABC"));
    }

    public String minWindow(String s, String t) {
   
        Map<Character,Integer> tMap = new HashMap<>();
        Map<Character,Integer> windowMap = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
   
            tMap.put(t.charAt(i),tMap.getOrDefault(t.charAt(i),0)+1);
        }
        int left = 0, begin = 0, minLen = Integer.MAX_VALUE;
        char[] sArray = s.toCharArray();
        for (int right = 0; right < s.length() && minLen!=t.length(); right++) {
   
            //如果为窗口需要的元素
            if (t.indexOf(sArray[right])!=-1){
   
                //窗口记录所有的需要元素的数量
                windowMap.put(sArray[right],windowMap.getOrDefault(sArray[right],0)+1);
                //如果窗口包含全部所需元素
                if (check(windowMap,tMap)){
   
                    //获取窗口最左边元素
                    //如果最左边元素为不需要的元素;或者为窗口拥有的该需要元素已经多于实际需要的元素数量
                    while (tMap.get(sArray[left])==null || windowMap.get(sArray[left])-1>=tMap.get(sArray[left])){
   
                        //窗口减少该元素
                        windowMap.put(sArray[left],windowMap.getOrDefault(sArray[left],1)-1);
                        //并实现左边界右移
                        left++;
                    }
                }
            }
            if (check(windowMap,tMap) && minLen > right-left+1){
   
                minLen = right-left+1;
                begin = left;
            }
        }
        if (minLen==Integer.MAX_VALUE) return "";
        return s.substring(begin,begin+minLen);
    }

    /** * 检查窗口拥有的元素是否包含所需要的所有元素 * @param windowMap * @param tMap * @return */
    public boolean check(Map<Character,Integer> windowMap, Map<Character,Integer> tMap){
   
        for (Character ch : tMap.keySet()){
   
            if (tMap.get(ch)>windowMap.getOrDefault(ch,0)){
   
                return false;
            }
        }
        return true;
    }

}

另外提供力扣官方提供的参考:方法一:滑动窗口 。上述示例解题思路和官方思路非常相似,但我感觉按照自己思路实现的代码更容易理解和看懂。

本文来源MrKorbin,由架构君转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/25253

发表评论