专栏首页算法半岛LeetCode-3 无重复字符的最长子串

LeetCode-3 无重复字符的最长子串

> 题目:3. 无重复字符的最长子串

> 难度:中等

> 分类:字符串

> 解决方案:双指针、滑动窗口

LeetCode前几道题都是经典题,今天我们学习第3题无重复字符的最长子串,这道题在秋招面试中遇见过,再次相遇,如此亲切。下面我们看看这道题的题目描述。

题目描述

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

示例1:

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

示例2:

输入: "bbbbb"输出: 1解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例3:

输入: "pwwkew"输出: 3解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。     请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

分析

首先我们看看这个题的示例3,该示例中提示我们这个题求字符串的子串而不是子序列,我们具体来看看什么是子串,什么是子序列。

子串:字符串中任意个连续的字符组成的子序列称为该串的子串。注意子串强调字符的连续性。如图1所示。 子序列:字符串中去掉任意个元素后得到的结果即为该字符串的子序列。注意子序列中字符出现的次序与原字符串中字符出现的次序要保持一致。如图2所示。

[图1. 子串]

[图2. 子序列]

区分子串和子序列后,我们再回过头来看看这个题。我们先动手画一画示例1的解题过程,如图3所示:

[图3. 示例1分析过程图解]

从上图我们可以观察出,可以使用双指针( left指针和 right指针)来维护一个滑动窗口,这个窗口内的字符都是没有重复的,遍历一趟字符串后就可以得到最大的子串,因此时间复杂度为 O(n)。现在想一个问题:right指针指向的字符怎么确定它在前面是否出现过,若出现过,它出现的位置在哪儿?对于这个问题,做过LeetCode-1 两数之和这道题的小伙伴们应该知道,我们可以使用 HashMap记录一个字符是否出现以及出现后的位置。对于重复多次出现的字符,我们是保留所有出现的位置还是只记录一个位置?观察示例1分析过程可以知道,我们只需要保存一个最大位置即可。还有一个关键点,我们如何确定 left指针的位置?这一点非常重要,需要分情况讨论。

  • 当目前 right指针指向的字符未出现过, left指针不需要移动;
  • 当目前 right指针指向的字符出现过,如果该字符在窗口中,即该字符出现在当前 left指针的右边,则通过 HashMap获取字符的位置并向右移动一位即为更新后 left的位置;如果该字符在窗口外面,即在当前 left指针的左边,则不需要移动 left的位置。

分析完后,再看看 java代码的具体实现:

class Solution {    public int lengthOfLongestSubstring(String s) {        int res = 0;        if(s.length() == 0)            return res;        // 创建HashMap,用来保存字符与位置之间的对应关系        HashMap<Character, Integer> hashMap = new HashMap<>();        // 初始化左指针和右指针,并遍历字符串        for(int left = 0, right = 0; right < s.length(); right++){            // 判断右指针指向的字符是否出现过            if(hashMap.containsKey(s.charAt(right))){                // 确定左指针的位置                left = Math.max(left, hashMap.get(s.charAt(right))+1);            }            // 对于第一次出现的字符,保存该字符的位置;对于多次出现的字符,更新该字符出现的位置            hashMap.put(s.charAt(right), right);            // 更新窗口的大小,保存最大的窗口大小            res = Math.max(res, right-left+1);        }        return res;    }}

整个算法流程的时间复杂度为 O(n),空间复杂度为 O(1)

Github地址

LeetCode-3 无重复字符的最长子串:https://github.com/JacobLei/leetcode/blob/master/src/main/java/A3_LongestSubstringWithoutRepeatingCharacters.java

参考链接

无重复字符的最长子串:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/

本文分享自微信公众号 - 算法半岛(jacob2359),作者:jacob2359

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-05-12

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode-5 最长回文子串

    今天我们学习第5题最长回文子串,这是一个字符串的中等题,像这样字符串的题目经常作为面试题来考察面试者算法能力和写代码能力,因此最好能手写出该题。下面我们...

    用户3470542
  • LeetCode-8 字符串转换整数

    今天我们学习第8题字符串转换整数,这是一个字符串的中等题,像这样字符串的题目经常作为面试题来考察面试者算法能力和写代码能力,因此最好能手写出该题。下面我...

    用户3470542
  • LeetCode-11 盛最多水的容器

    今天我们学习第11题盛最多水的容器,这是一个数组的中等题,这个题目难度不大,记得在秋招面试中遇见过。下面我们看看这道题的题目描述。

    用户3470542
  • 数学之美?编程之美?数学 + 编程= unbelievable 美!

    本文所要介绍这个案例,整个实现过程其实并没有多么难多么复杂,但从实际问题到模型建立的思维推导过程,笔者认为还是很有意思也很有意义的,所以,也希望能够分享给大家。

    Rusu
  • 拿什么拯救你,我的offer!(从零打卡刷Leetcode——No.005)

    小詹此记录贴的读者越来越少了,也许是小詹总结的不够好欢迎留言区提出宝贵的意见!也欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一...

    小小詹同学
  • 定点数的表示方法

    计算机中数值的表示有两种形式,一是定点数(Fixed-point Number),二是浮点数(Floating-point Number)。

    Dabelv
  • 定点数的表示方法

    计算机中数值的表示有两种形式,一是定点数(Fixed-point Number),二是浮点数(Floating-point Number)。

    Dabelv
  • zookeeper-3.4.10的安装配置

    leader:能接收所有的读写请求,也可以处理所有的读写请求,而且整个集群中的所有写数据请求都是由leader进行处理 follower:能接收所有的读写请求...

    CoderJed
  • 纳德拉的挑战:拯救微软

    8月12日消息,据国外媒体报道,最近,在与著名科技博客作者Ed Bott关于微软未来的讨论中,公众相信Ed的论点——萨帝亚·纳德拉作为CEO,会为微软带来更光明...

    静一
  • 学界 | 堆叠解卷积网络实现图像语义分割顶尖效果

    选自arXiv 机器之心编译 参与:路雪 本文介绍了一种堆叠解卷积网络(Stacked Deconvolutional Network),它可用于高效的图像语义...

    机器之心

扫码关注云+社区

领取腾讯云代金券