面试真题:无重复字符的最长子串-阿里云开发者社区

开发者社区> 看山灬> 正文

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

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

image.png

你好,我是看山。


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


先看一下题目描述:


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


输入:s = “abcabcbb”

输出:3

解释:因为无重复字符的最长子串是 “abc”,所以其长度为 3。


输入:s = “pwwkew”

输出:3

解释:因为无重复字符的最长子串是 “wke”,所以其长度为 3。


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


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


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


来个图例:

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


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


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

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

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


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

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
一文快速搞定Redis_数据类型及JavaApi操作
大家好,我是**ChinaManor**,直译过来就是中国码农的意思,我希望自己能成为国家复兴道路的铺路人,大数据领域的耕耘者,平凡但不甘于平庸的人。
9 0
什么是机器学习| 学习笔记
快速学习什么是机器学习
4 0
数据结构排序算法
数据结构排序算法
3 0
偏序关系
偏序 关系 离散数学
6 0
无监督学习算法(上)| 学习笔记
快速学习无监督学习算法(上)
4 0
Elasticsearch最佳实践建议
本文主要是总结了Elasticsearch从安装、配置到应用程序使用、运维、性能优化的最佳实践的建议,希望能对于Elasticsearch的开发和运维提供一些帮助。
6 0
PG+MySQL第9课-实时精准营销
通常业务场景会涉及基于标签条件圈选目标客户、基于用户特征值扩选相似人群、群体用户画像分析这些技术,本文将围绕这三个场景去介绍在实施精准营销里面的PG数据库的使用
10 0
分布式一致性和分布式事务之间的关系
在开源的背景下,数据库的分布式也占据了重要的地位。
5 0
无监督学习算法(下)| 学习笔记
快速学习无监督学习算法(下)
6 0
其他学习算法| 学习笔记
快速学习其他学习算法
5 0
+关注
看山灬
专注后端开发、架构相关知识分享,个人网站 https://howardliu.cn/。
136
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载