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

布满荆棘的人生 2022-12-28 01:47 137阅读 0赞

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

## 1、参考资料 ##

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

## 2、题目要求 ##

> **题目要求：**

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

> **示例 1:**

输入: `"abcabcbb"`

输出: `3`

解释: 因为无重复字符的最长子串是 `"abc"`，所以其长度为 `3`。

> **示例 2:**

输入: `"bbbbb"`

输出: `1`

解释: 因为无重复字符的最长子串是 `"b"`，所以其长度为 `1`。

> **示例 3:**

输入: `"pwwkew"`

输出: `3`

解释: 因为无重复字符的最长子串是 `"wke"`，所以其长度为 `3`。

请注意，你的答案必须是 子串 的长度，`"pwke"` 是一个子序列，不是子串。

## 3、代码思路 ##

滑动窗口法：定义两个指针，`startIndex` 和 `endIndex` ，代表当前窗口的开始和结束位置，使用 `hashset`，当窗口中出现重复的字符时，`startIndex ++`没有重复时，`endIndex ++`，并更新长度的最大值，时间复杂度 `o(n)`

> **举例说明：**

1.  比如 `"pwwkew "` 字符串
2.  初始时 `startIndex = 0` ，`endIndex = 0` ，均指向第一个字符串中第一个字符
3.  `endIndex` 扫描到第一个字符 `'p'` ，发现 `HashSet` 中没有，添加至 `HashSet` 中，`endIndex` 后移
    
    ![image-20200723094405548][]
4.  `endIndex` 扫描到字符 `'w'` ，发现 `HashSet` 中没有，添加至 `HashSet` 中，`endIndex` 后移
    
    ![image-20200723094627395][]
5.  `endIndex` 扫描到字符 `'w'` ，发现 `HashSet` 存在该字符，尝试着将其从 `HashSet` 中删除
6.  为什么我要说尝试着删除？因为每次我们在 `HashSet` 中删除的是 `startIndex` 索引处的字符，这可能并不是与当前 `endIndex` 处字符互相重复的字符，比如 `"abcb"`
7.  删除字符后，`startIndex` 别忘了后移
8.  直到 `HashSet` 中不存在重复字符为止
    
    ![image-20200723094757570][]
9.  执行上述删除操作后，`startIndex` 和 `endIndex` 均指向 `'w'` ，此时 `HashSet` 中没有 `'w'`（上一步给删了），将 `'w'` 添加至 `HashSet` 中， `endIndex` 后移
    
    ![image-20200723095824347][]
10. 什么时候停止？`endIndex < str.length()` ，当 `endIndex` 扫描字符串最后一位后，`endIndex` 后移一位，此时 `endIndex == str.length()` ，说明字符串已经扫描完毕

## 4、代码实现 ##

代码

public static void main(String[] args) {
        
    
        int max = maxSubStrLenWithNoRepearChar("pwwkew");
        System.out.println(max);
    
    }
    
    public static int maxSubStrLenWithNoRepearChar(String str) {
        
        // 起始索引
        int startIndex = 0;
        // 结束索引
        int endIndex = 0;
        // 字符串长度
        int strLen = str.length();
        // HashSet 用于判断是否有重复字符
        Set<Character> set = new HashSet<Character>();
        // 无重复字符的字串的最大长度
        int maxLength = 0;
    
        // 扫描到字符串结尾
        while (endIndex < strLen) {
        
            // 如果 HashSet 中已经有此字符
            if (set.contains(str.charAt(endIndex))) {
        
                set.remove(str.charAt(startIndex++));
            } else {
        
                // 否则 HashSet 还没有此字符，向 HashSet 中添加此字符
                set.add(str.charAt(endIndex++));
                // 计算子串最大长度
                maxLength = Math.max(maxLength, endIndex- startIndex);
            }
        }
    
        return maxLength;
    }

[3.]: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
[image-20200723094405548]: /images/20221120/215ba9b240b64bbaa74f536a0e1f521f.png
[image-20200723094627395]: /images/20221120/e29edc507be947e181cefd0b6777a09b.png
[image-20200723094757570]: https://img-blog.csdnimg.cn/img_convert/e25c4bc48a5162e70ed38bfc27a48da3.png
[image-20200723095824347]: https://img-blog.csdnimg.cn/img_convert/db15fb0e7cd418ab91cc90423ef6d43f.png