写点什么

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

用户头像
看山
关注
发布于: 2021 年 05 月 08 日
面试真题:无重复字符的最长子串

你好,我是看山。


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


先看一下题目描述:


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

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

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

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


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


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


来个图例:



根据图例写代码:


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 也给过定义:


双指针从广义上来说,是指用两个变量在线性结构上遍历而解决的问题。狭义上说,

  • 对于数组,指两个变量在数组上相向移动解决的问题;

  • 对于链表,指两个变量在链表上同向移动解决的问题,也称为「快慢指针」问题。

双指针算法通常不难,是基于暴力解法的优化,它们是很好的学习算法的入门问题


这里 可以找到所有 LeetCode 中关于双指针解法的题目,可以过足瘾。


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



发布于: 2021 年 05 月 08 日阅读数: 9
用户头像

看山

关注

公众号「看山的小屋」 2017.10.26 加入

游于码界,戏享人生。 未来不迎,当时不杂,既过不恋。

评论

发布
暂无评论
面试真题:无重复字符的最长子串