【字符串】最长不含重复字符的子字符串

水深无声 2022-11-26 07:59 141阅读 0赞

# 1. 题目描述 #

题目链接：[最长不含重复字符的子字符串][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70]

# 2. 题目分析 #

1.  我们可以看到，题目要求我们求在一个区间内不含有重复的字符串，这种区间，我们第一时间应该想到滑动窗口。
2.  这个题目的巧妙在于:我们利用HashMap的key存储字符，利用value存储当前的下标
3.  当我们的key重复时，也就证明当前窗口中的字符串不是重复的，需要将左边界的窗口下标进行修改，直接让 **左边界的下标 = value + 1** 这样的话，避免了一些重复的操作，比如样例：**poujhwwer**
4.  为什么要和原来的left比较呢？ 因为我们记录的是重复的，如果像**abba**这样，就会发生错误。
5.  每次进行操作都算一下滑动窗口中的大小，最后输出count。

# 3. 题目代码 #

class Solution {
        
        public int lengthOfLongestSubstring(String s) {
        
            int left = 0;
    		int count = 0;
    		HashMap<Character, Integer> map = new HashMap<Character, Integer>();
    		for (int right = 0; right < s.length(); right++) {
        
    			if (map.containsKey(s.charAt(right))) {
        
    				left = Math.max(left, map.get(s.charAt(right)) + 1);
    			}
    			map.put(s.charAt(right), right);
    			count = Math.max(count,right-left + 1);
    		}
    		return count;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70_pic_center]

[Link 1]: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70]: /images/20221124/7690b956c9e6439bae5b316a9df5a871.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/bd92f46a2bf04cebb0b39b56f9983e13.png