LeetCode_3_无重复字符的最长子串
题目
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
1 | 输入: "abcabcbb" |
示例 2:
1 | 输入: "bbbbb" |
示例 3:
1 | 输入: "pwwkew" |
Related Topics
- 哈希表
- 双指针
- 字符串
- Sliding Window
解法
双指针法
假设两个指针,一个标记开始索引
,一个标记结束索引
,同时准备一个遍历过的字符的HASH表。
指针均从0位开始,结束索引
遇到一个字符分为两个情况:
- 该字符不在HASH表中:HASH表中加入这个字符的索引,同时结束索引继续往后遍历
- 该字符在HASH表中:
- 开始索引大于该字符的索引:结束索引继续往后遍历就行
- 开始索引小于等于该字符的索引:更新该字符的索引,同时开始索引变为该字符索引+1,结束索引+1
时间复杂度
:$O(n)=n$空间复杂度
:$O(n)=n$
1 | class Solution: |
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Tomorrow!
评论