LeetCode: 3. Longest Substring Without Repeating Characters

引言

题目链接:https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

题目大意

输入一个字符串,输出没有重复字符的最长子串的长度。

例:

  • Example1

Input: "abcabcbb"

Output: 3

Explanation: The answer is "abc", with the length of 3.

  • Example2

Input: "bbbbb"

Output: 1

Explanation: The answer is "b", with the length of 1.

题解

一句话题解:利用map或者hash表映射字符和字符上一次出现的位置,当遇到重复字符时(当前符合条件子串结束),查找下一个不包含重复字符的子串起点,同时把当前子串的长度和已有最大值比对记录

  • 详解

映射关系中,保存当前字符在字符串已查询部分中最后出现的下标位置(默认 -1,没有出现过)

  1. 默认第一个子串起点下标为0
  2. 最大值为当前下标和起点下标的差值与存储的最大值的较大者
  3. 当查询到当前字符已经出现过,分两种情况讨论

a). 当前子串的起点下标 > 当前查询字符上一次出现下标位置(证明当前查询字符在当前子串未出现过,如 tmmzuxt,查询最后一个 t当前子串起点为第二个 m

b). 当前子串的起点下标 <= 当前查询字符上一次出现下标位置(证明当前查询字符在当前子串已经出现过一次,当前字符串终结,如 wkew,查询最后一个 w当前子串起点为第一个 w

综上所述,情况一当前子串起点位置大于查询字符上一次出现位置,字符在子串第一次出现,保持起点不变即可,情况二当前子串起点位置小于查询字符第一次出现位置,字符在子串第二次出现,当前子串终结,下一个子串起点重置为当前查询字符出现的下一个下标

lastDiffIndex = lastDiffIndex > index + 1 ? lastDiffIndex : index + 1;

复杂度 O(n)

AC代码

c++版本

go版本

繁夜

发表评论


:[微笑]::[撇嘴]::[色]::[发呆]::[得意]::[流泪]::[害羞]::[闭嘴]::[睡]::[大哭]::[尴尬]::[发怒]::[调皮]::[呲牙]::[惊讶]::[难过]::[酷]::[冷汗]::[抓狂]::[吐]::[偷笑]::[可爱]::[白眼]::[傲慢]::[饥饿]::[困]::[惊恐]::[流汗]::[憨笑]::[大兵]::[奋斗]::[咒骂]::[疑问]::[嘘...]::[晕]::[折磨]::[衰]::[骷髅]::[敲打]::[再见]::[擦汗]::[抠鼻]::[鼓掌]::[糗大了]::[坏笑]::[左哼哼]::[右哼哼]::[哈欠]::[鄙视]::[委屈]::[快哭了]::[阴险]::[亲亲]::[吓]::[可怜]::[笑哭]::[doge]::[泪奔]::[无奈]::[托腮]::[斜眼笑]::[喷血]::[惊喜]::[骚扰]::[小纠结]::[我最美]::[羊驼]::[幽灵]::[吃]::[OK]::[爱你]::[抱拳]::[勾引]::[强]::[弱]::[拳头]::[爱心]::[喝彩]::[西瓜]::[啤酒]::[玫瑰]::[凋谢]::[礼物]::[拥抱]::[月亮]::[菊花]::[棒棒糖]::[蛋]::[刀]::[菜刀]::[炸弹]::[手枪]:

刷新评论