面试真题：无重复字符的最长子串

心已赠人 2021-09-25 08:40 217阅读 0赞

![面试真题：无重复字符的最长子串][82809ddeddadc7c123d3a62d19d7737e.png]

你好，我是看山。

来一个算法题，面试之后查了一下，是 LeetCode 的第三题，难度中等。居然在面试过程中碰到 LeetCode 真题，事后总结一波。加深印象。

先看一下题目描述：

> 给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。
> 
> 输入：s = “abcabcbb”  
> 输出：3  
> 解释：因为无重复字符的最长子串是 “abc”，所以其长度为 3。
> 
> 输入：s = “pwwkew”  
> 输出：3  
> 解释：因为无重复字符的最长子串是 “wke”，所以其长度为 3。
> 
> 请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

看过题目之后，我最先想到的是一道数学题：一个线段上有 10 个点，求总共有多少的线段？如果是小朋友解题的话，一般就是，左手固定，右手向右移动，每移动一个点就加一个数，右手移动到末尾后，左手向右移动一个点，以此类推，知道最后一个点。这样就能够数出所有的线段数量，而且还不会乱。

其实上面这个算法题和我说的这个数学题的解法类似，采用小学生解法，只不过需要在数数的时候加一些判断，比如，线段中的点，有没有相同的。

来个图例：

![无重复字符的最长子串][1fb376658723002306cd4ab8fc40f420.png]

根据图例写代码：

import java.util.HashSet;
    import java.util.Set;
    
    class Solution { 
        public static int lengthOfLongestSubstring(String s) { 
            if (s == null || s.isEmpty()) { 
                return 0;
            }
            final int len = s.length();
            final Set<Character> sets = new HashSet<>();
            int i = 0, j = 0, result = 0;
            Character tmp ;
            while (i < len && j < len) { 
                tmp = s.charAt(j);
                if (sets.contains(tmp)) { 
                    sets.remove(s.charAt(i++));
                } else { 
                    sets.add(tmp);
                    result = Math.max(result, j++ - i + 1);
                }
            }
            return result;
        }
    }

如果是面试，这个时候就可以交差了。既然是总结，就得再想一下这个解法有没有通用性。我们所采用的办法是，通过两个变量 i 和 j 指向计算元素，然后与 i 与 j 之间的元素进行判断，这种方式江湖称之为“双指针”。贴心的 LeetCode 也给过定义：

> 双指针从广义上来说，是指用两个变量在线性结构上遍历而解决的问题。狭义上说，
> 
>  *  对于数组，指两个变量在数组上相向移动解决的问题；
>  *  对于链表，指两个变量在链表上同向移动解决的问题，也称为「快慢指针」问题。
> 
> 双指针算法通常不难，是基于暴力解法的优化，**它们是很好的学习算法的入门问题**。

从 [这里][Link 1] 可以找到所有 LeetCode 中关于双指针解法的题目，可以过足瘾。

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

你好，我是看山，公众号：看山的小屋，10 年老猿，Apache Storm、WxJava、Cynomys 开源贡献者。游于码界，戏享人生。

个人主页：[https://www.howardliu.cn][https_www.howardliu.cn]  
个人博文：[面试真题：无重复字符的最长子串][Link 2]  
CSDN 主页：[http://blog.csdn.net/liuxinghao][http_blog.csdn.net_liuxinghao]  
CSDN 博文：[面试真题：无重复字符的最长子串][Link 3]

![公众号：看山的小屋][21785bb43b333b0ff8efda479e715378.png]

[82809ddeddadc7c123d3a62d19d7737e.png]: /images/20210923/a51273d6c9044dbcae38d170151ce32a.png
[1fb376658723002306cd4ab8fc40f420.png]: /images/20210923/a4eda2940cac4c00994017204bb6f2c8.png
[Link 1]: https://leetcode-cn.com/tag/two-pointers/problemset/
[https_www.howardliu.cn]: https://www.howardliu.cn
[Link 2]: https://www.howardliu.cn/longest-substring-without-repeating-character/
[http_blog.csdn.net_liuxinghao]: http://blog.csdn.net/liuxinghao
[Link 3]: https://blog.csdn.net/liuxinghao/article/details/116545038
[21785bb43b333b0ff8efda479e715378.png]: /images/20210923/265d00aab3fd435a8c8c954f5ff7dad8.png