专栏首页木又AI帮打卡群2刷题总结1004——无重复字符的最长子串

打卡群2刷题总结1004——无重复字符的最长子串


leetcode第3题:无重复字符的最长子串

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/


【题目】

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

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

【思路】

1、暴力破解:两层for循环,遍历所有子串,判断是否有重复元素,并记录最长子串长度。

2、hash表:遍历数组,使用hash存储元素及其下标。遍历时,当元素nums[i]存在于hash表时,需要更新其下标,同时更新最长子串长度。

【代码】

python版本

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        d = {}
        last_index = 0
        res = 0
        for i, si in enumerate(s):
            # 在dict中,则子串长度可能更长
            # last_index更新为d[si] + 1
            if si in d and d[si] >= last_index:
                res = max(res, i - last_index)
                last_index = d[si] + 1
            
            # 更新dict的si
            d[si] = i
            
        # 注意,还未和最后一段进行比较
        res = max(res, len(s) - last_index)
        return res

【相似题目】

290. 单词规律

解题思路:两个hash 表,观察pattern和str是否一一对应。

349. 两个数组的交集

解题思路:两个集合的交集。

350. 两个数组的交集 II

解题思路:hash表,统计两个数组的元素及出现次数,再求交集。

本文分享自微信公众号 - 木又AI帮(gh_eaa31cab4b91),作者:木又

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

原始发表时间:2020-10-05

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【leetcode刷题】T58-无重复字符的最长子串

    但是,很多子串是不用判断的,比如说,s="abcacbd",那么子串“abcac”、"abcacb"等不用判断,因为“abca”已经存在重复元素。

    木又AI帮
  • 【leetcode刷题】20T3-无重复字符的最长子串

    https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

    木又AI帮
  • 3. 无重复字符的最长子串--题解

    付威
  • Python 版 LeetCode 刷题笔记 #3 无重复字符的最长子串

    今天这题目乍一看,在字符串中找来遍历即可,但实际操作下来,还是有些复杂的,也配得上其中等难度的定位了。

    TTTEED
  • 003. 无重复字符的最长子串 | Leetcode题解

    题目要求连续, 我们考虑使用滑动窗口。而这道题就是窗口大小不固定的滑动窗口题目,然后让我们求满足条件的窗口大小的最大值,这是一种非常常见的滑动窗口题目。

    苏南
  • 【刷穿 LeetCode】3. 无重复字符的最长子串(中等)

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

    宫水三叶的刷题日记
  • Python 版 LeetCode 刷题笔记 #5 无重复字符的最长子串(下)

    给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例:

    TTTEED
  • Python 版 LeetCode 刷题笔记 #5 无重复字符的最长子串(上)

    从下午三点半到晚上十二点,一直卡在这个题,郁闷。经过好几番尝试后,用暴力法完成并提交了一版代码,测试结果超出时间限制。根据反馈的测试用例,专门针对特例做了下处理...

    TTTEED
  • 图解LeetCode第 3 号问题:无重复字符的最长子串

    LeetCode上第 3 号问题:Longest Substring Without Repeating Characters。

    五分钟学算法
  • 杭电OJ刷题指南

    说起来刷题,很多大牛都会推荐LeetCode或者牛客网,这两个网站是刷题的好网站。但对新手来说,有一点难度,新手建议先去杭电OJ刷题,这里的题目难度不大,如果你...

    Jasonangel
  • LeetCode(1-两数之和&&2-两数相加&&3-无重复字符的最长子串)

    我们主要通过map的数据类型进行存储,主要是因为map能够直接根据key来直接获取value,这就使得我们后面获取数组下标的过程更加方便.

    萌萌哒的瓤瓤
  • C# 算法题系列(一) 两数之和、无重复字符的最长子串

    原题链接 https://leetcode-cn.com/problems/two-sum/

    痴者工良
  • 力扣 (LeetCode)-28. 实现 strStr()|刷题打卡

    Github来源:力扣 (LeetCode)|刷题打卡 | 求星星 ✨ | 给个❤️关注,❤️点赞,❤️鼓励一下作者

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

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

    小小詹同学
  • Linux三剑客之sed

    程序员同行者
  • 力扣 (LeetCode)-14. 最长公共前缀|刷题打卡

    每天学习编程,让你离梦想更新一步,感谢不负每一份热爱编程的程序员,不论知识点多么奇葩,和我一起,让那一颗四处流荡的心定下来,一直走下去,加油,2021加油!欢迎...

    达达前端
  • 每日算法题:Day 14(数据结构)

    输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,c...

    算法工程师之路
  • 【刷题】2020最新剑指Offer汇总

    新手村 关卡1-1 洛谷的第一个任务 P1000 超级玛丽游戏:点击这里 P1001 A+B Problem:点击这里 P1421 小玉买文具:点击这里...

    瑞新
  • 轻松搞定RocketMQ入门

    (1)NameServer是一个几乎无状态的节点,可集群部署,节点之间无任何信息同步

    烂猪皮

扫码关注云+社区

领取腾讯云代金券