[Java·算法·中等]LeetCode3. 无重复字符的最长子串

不念不忘少年蓝@ 2023-09-24 20:36 20阅读 0赞

#### 每天一题，防止痴呆 ####

*  题目
 *  示例
 *  分析思路1
 *  题解1
 *  分析思路2
 *  题解2

## 题目 ##

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

## 示例 ##

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

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

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

## 分析思路1 ##

该算法使用了滑动窗口的思想，使用两个指针i和j分别表示当前子串的左右边界。使用一个set来记录当前子串中出现过的字符，当set中不存在s\[j\]时，将其添加到set中，更新最长子串长度，并将j指针后移；当set中已经存在s\[j\]时，将set中的s\[i\]删除，i指针后移。这样每次移动指针时，都保证了子串中没有重复的字符。

在遍历过程中，使用ans来记录最长子串的长度，最终返回ans即可。

## 题解1 ##

class Solution {
        
        public int lengthOfLongestSubstring(String s) {
        
            Set<Character> set = new HashSet();
            int i = 0,j=0,longest=0;
            int len = s.length();
            while (i<len && j<len){
        
                if(!set.contains(s.charAt(j))){
        
                    set.add(s.charAt(j++));
                    longest = Math.max(longest, j-i);
                }else {
        
                    set.remove(s.charAt(i++));
                }
            }
            return longest;
        }
    }

执行结果（写的不好，不推荐。用第二种方法吧。）  
![!\[在这里插入图片描述\](https://img-blog.csdnimg.cn/08b06d391f084e39999fb3a53fe77a01.png][https_img-blog.csdnimg.cn_08b06d391f084e39999fb3a53fe77a01.png]

## 分析思路2 ##

定义一个 map 数据结构存储 (k, v)，其中 key 值为字符，value 值直接存字符的下标  
我们定义不重复子串的开始位置为 start，结束位置为 end  
随着 end 不断遍历向后，会遇到与 \[start, end\] 区间内字符相同的情况，此时将字符作为 key 值，获取其 value 值，并更新 start，此时 \[start, end\] 区间内不存在重复字符  
无论是否更新 start，都会更新其 map 数据结构和结果 ans。

## 题解2 ##

class Solution {
        
        public int lengthOfLongestSubstring(String s) {
        
            int len = s.length();
            int maxLen = 0;
            Map<Character,Integer> map = new HashMap<>();
            for (int start=0,end=0; end<len; end++){
        
                char c = s.charAt(end);
                if(map.containsKey(c)){
        
                	// +1表示从该位置之后开始寻找不重复子串
                    start = Math.max(start, map.get(c)+1);
                }
                maxLen = Math.max(maxLen, end-start+1);
                map.put(c, end);
            }
            return maxLen;
        }
    }

执行结果  
![在这里插入图片描述][cd66bbdef97e4e9e80801383a99d3974.png]

[https_img-blog.csdnimg.cn_08b06d391f084e39999fb3a53fe77a01.png]: https://img-blog.csdnimg.cn/a4fe0a3a561b4ce282ffc07f712ddd47.png
[cd66bbdef97e4e9e80801383a99d3974.png]: https://img-blog.csdnimg.cn/cd66bbdef97e4e9e80801383a99d3974.png