3. 无重复字符的最长子串（滑动窗口）

妖狐艹你老母 2023-10-05 20:12 21阅读 0赞

#### 3. 无重复字符的最长子串 ####

*  题目
 *  解题思路
 *  代码

## 题目 ##

给定一个字符串，请你找出其中不含有重复字符的 **最长子串** 的长度。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]  
提示：

*  0 <= s.length <= 5 \* 104
 *  s 由英文字母、数字、符号和空格组成

## 解题思路 ##

套用模板即可，因为只有一个字符串，所以模板还可以简化一下，不需要`need`和`valid`。

更新窗口内数据只要更新window内该字符出现的次数就可以了。

还要注意更新结果是在收缩窗口之后。要保证无重复字符串，那么哪一个窗口是没有重复的字符串呢？回头看一下我们收缩窗口的条件：`存在重复元素`，所以我们收缩窗口之后的那个窗口是一定没有重复元素的。

## 代码 ##

class Solution {
        
        public int lengthOfLongestSubstring(String s) {
        
            Map<Character, Integer> window = new HashMap<>();
            int left = 0;
            int right = 0;
            int res = 0;//记录结果
    
            while (right < s.length()) {
        
                char c = s.charAt(right);
                right++;
                //进行窗口内数据的更新
                window.put(c, window.getOrDefault(c, 0) + 1);
    
                //说明有重复的字串出现，因为名称为c的字符出现的次数大于1了，不符合条件
                while (window.getOrDefault(c, 0) > 1) {
        
                    char d = s.charAt(left);
                    left++;
                    //进行窗口内数据的更新
                    window.put(d, window.getOrDefault(d, 0) - 1);
                }
    
                //在这里更新答案
                res = Math.max(res, right - left);
    
            }
            return res;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210222223059164.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70