目录
  1. 1. 题目
  2. 2. DEMO
  3. 3. 解法
    1. 3.1. 双指针法
lengthOfLongestSubstring

题目

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

DEMO

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


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


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

解法

双指针法

将整个字符串分解成各个字母对应的位图

abcabcbb分解为

  • a:10010000
  • b:01001011
  • c:00100100

采取双指针,首指针依次从首位向右移动,次指针跟随首指针,且最多比其向右偏移字母个数的偏移量。当任意一个字母的1在指针间出现两次则记录指针偏移差,并右移首指针后重复次指针的操作。

1
def
文章作者: ZyTomorrow
文章链接: https://zytomorrow.top/2019/06/03/leetcode/lengthoflongestsubstring/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Tomorrow
打赏
  • 微信
  • 支付寶

评论