Leetcode 3. 无重复字符的最长子串(滑动窗口YYDS)

Love The Way You Lie 2022-08-31 12:26 168阅读 0赞

#### 题目重述 ####

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

##### 示例 1: #####

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

##### 示例 2: #####

输入: s = “bbbbb”  
输出: 1  
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

##### 示例 3: #####

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

##### 示例 4: #####

输入: s = “”  
输出: 0

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#### 思路 ####

本题使用滑动窗口算法实现。

维护一个map作为窗口，维护双指针初始化为0，标识窗口的范围，不断扩张，直到出现重复元素，开始缩减，在上述过程中，不断更新子串的最大长度即可。

#### Java实现 ####

class Solution {
        
        public int lengthOfLongestSubstring(String s) {
        
            if(s==null || "".equals(s))
            {
        
                return 0;
            }
             Map<Character,Integer> window = new HashMap<>();
             int left = 0,right = 0,maxLen = 0;
             // 扩张
             while (right<s.length())
             {
        
                 char c = s.charAt(right);
                 right++;
                 window.put(c,window.getOrDefault(c,0)+1);
                 // 收缩，当窗口中出现重复元素时候
                 while (window.get(c) > 1)
                 {
        
                     // 需要移除窗口的元素
                     char d = s.charAt(left);
                     left++;
                     window.put(d,window.getOrDefault(d,0)-1);
                 }
                 // 更新
                 maxLen = Math.max(maxLen,right-left);
             }
             return maxLen;
        }
    }