三、无重复字符的最长子串

╰半夏微凉° 2021-09-25 00:52 258阅读 0赞

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

*  题目描述
 *  算法解析
 *  代码

# 题目描述 #

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

# 算法解析 #

> 以示例一中的字符串 abcabcbb 为例，找出从每一个字符开始的，不包含重复字符的最长子串，那么其中最长的那个字符串即为答案。对于示例一中的字符串，我们列举出这些结果，其中括号中表示选中的字符以及最长的字符串：
> 
>  *  以 (a)bcabcbb 开始的最长字符串为 (abc)abcbb
>  *  以 a(b)cabcbb 开始的最长字符串为 a(bca)bcbb
>  *  以 ab\[c\]abcbb 开始的最长字符串为 ab(cab)cbb
>  *  以 abc(a)bcbb 开始的最长字符串为 abc(abc)bb
>  *  以 abca(b)cbb 开始的最长字符串为 abca(bc)bb
>  *  以 abcab\[c\]bb 开始的最长字符串为 abcab(cb)b
>  *  以 abcabc(b)b 开始的最长字符串为 abcabc(b)b
>  *  以 abcabcb(b) 开始的最长字符串为 abcabcb(b)

# 代码 #

public int lengthOfLongestSubstring(String s) { 
         // 哈希集合，记录每个字符是否出现过
         Set<Character> occ = new HashSet<Character>();
         int n = s.length();
         // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
         int rk = -1, ans = 0;
         for (int i = 0; i < n; ++i) { 
             if (i != 0) { 
                 occ.remove(s.charAt(i - 1));  // 左指针向右移动一格，移除一个字符
             }
             while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) { 
                 // 不断地移动右指针
                 occ.add(s.charAt(rk + 1));
                 ++rk;
             }
             // 第 i 到 rk 个字符是一个极长的无重复字符子串
             ans = Math.max(ans, rk - i + 1);
         }
         return ans;
     }

--------------------

**博主的所有博客目录如下：[博客文章目录汇总][Link 1]  
Java面试部分的博客目录如下：[Java笔试面试目录][Java]**

> **转载请标明出处，原文地址：https://blog.csdn.net/weixin\_41835916 如果觉得本文对您有帮助，请点击顶支持一下，您的支持是我写作最大的动力，谢谢。  
> ![这里写图片描述][70]**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTgzNTkxNg_size_16_color_FFFFFF_t_70]: /images/20210923/89a5b0324a3645ae96feb77c790f0773.png
[Link 1]: https://blog.csdn.net/weixin_41835916/article/details/81879208
[Java]: https://blog.csdn.net/weixin_41835916/article/details/81413498
[70]: /images/20210923/a91a109ffc9b48c9a426f31176d4fba1.png