LeetCode算法之无重复字符的最长子串(滑动窗口法)

系统管理员 2022-02-17 04:15 141阅读 0赞

一.题目

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
    示例 1:
    输入: "abcabcbb"
    输出: 3 
    解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
    示例 2:
    输入: "bbbbb"
    输出: 1
    解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
    示例 3:
    输入: "pwwkew"
    输出: 3
    解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
         请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

二.方法一(暴力法)

class Solution {
        public int lengthOfLongestSubstring(String s) {
            
            int n = s.length();
            
            int ans = 0;
            
            for(int i = 0; i < n; i++){
                
                for(int j = i+1; j <= n; j++){        //双重for循环,取出字符串s中所有可能的子串
    
                    if(allUnique(s, i, j)){
                        
                        ans = Math.max(ans, j - i);         
                        
                    }
                
                }
                
                
            }
            
            
            return ans;
            
            
            
        }
        
        
        public boolean allUnique(String s, int start, int end){
    
            Set<Character> set = new HashSet<>();        //创建一个HashSet容器
            
            for(int i = start; i < end; i++){            //对子串进行遍历
                
                Character ch = s.charAt(i);
                
                if(set.contains(ch)){                    //如果set容器中有字符串ch,也就是存在重复字符,就返回false
    
                    return false;
                    
                }
                
                set.add(ch);                            //如果没有重复,则就将这个字符加进去
                
            }
            
            return true;
    
    
    
        }
            
            
            
    }

该方法虽然答案正确,但是会超出系统要求的时间范围.

三.方法二(滑动窗口)

class Solution {
        public int lengthOfLongestSubstring(String s) {
            
            int n = s.length();
            
            Set<Character> set = new HashSet<>();        //定义容器
            
            int ans = 0, i = 0, j = 0;
            
            while(i < n&& j < n){
                
                if(!set.contains(s.charAt(j))){        //不包含则向下执行
                    
                    set.add(s.charAt(j++));            //将该字符加到容器中
                    
                    ans = Math.max(ans, j - i);        //取ans和j-i中最大值,在该if条件下i不变,j递加
                    
                    
                }else{                                //如果包含该字符
                    
                    set.remove(s.charAt(i++));        //去掉容器中的首字符,因为首字符出现重复
                    
                    
                }
                
                
            }
            
            return ans;
            
        }
    }

思想:假设开始时选择的是字符串下标\[i, j\]的部分,如果下一个也就是第j+1个元素和第i个元素相同,则滑动窗口(据我的猜测,可能这就是滑动窗口的由来,这个地方竟然没表情来辅助一下~),滑动窗口的意思也就是i和j都加一,即现在所属的范围为\[i+1, j+1\],若没有触发滑动窗口的条件(第i个字符与第j+1个字符相同),则只有j+1,同时比较ans和j-i的值.

四.方法三(优化的滑动窗口)

public class Solution {
        public int lengthOfLongestSubstring(String s) {
            int n = s.length(), ans = 0;
            Map<Character, Integer> map = new HashMap<>(); // 创建一个容器
    
            for (int j = 0, i = 0; j < n; j++) {
                if (map.containsKey(s.charAt(j))) {        //包含键j
                    i = Math.max(map.get(s.charAt(j)), i);    //比较大小
                }
                ans = Math.max(ans, j - i + 1);            
                map.put(s.charAt(j), j + 1);
            }
            return ans;
        }
    }