- 难度: 中等
- 考察: 数组
- 来源: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
- 题解: https://github.com/azl397985856/leetcode/blob/master/problems/3.longestSubstringWithoutRepeatingCharacters.md
题目
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例1:
1 | 输入: "abcabcbb" |
示例2:
1 | 输入: "bbbbb" |
示例3:
1 | 输入: "pwwkew" |
思路
建立一个256位大小的整型数组 freg ,用来建立字符和其出现位置之间的映射。
维护一个滑动窗口,窗口内的都是没有重复的字符,去尽可能的扩大窗口的大小,窗口不停的向右滑动。
- 如果当前遍历到的字符从未出现过,那么直接扩大右边界;
- 如果当前遍历到的字符出现过,则缩小窗口(左边索引向右移动),然后继续观察当前遍历到的字符;
- 重复 1. 2. ,直到左边索引无法再移动;
- 维护一个结果res,每次用出现过的窗口大小来更新结果 res,最后返回 res 获取结果。
关键点
- 用一个 mapper 记录出现过并且没有被删除的字符
- 用一个滑动窗口记录当前 index 开始的最大的不重复的字符序列
- 用 res 去记录目前位置最大的长度,每次滑动窗口更新就去决定是否需要更新 res
复杂度
- 时间复杂度:O(N)
- 空间复杂度:O(N)
代码
1 | func lengthOfLongestSubstring(s string) int { |