文章目录
- 1.问题描述
- 2.难度等级
- 3.热门指数
- 4.解题思路
- 方法一：暴力法
- 方法二：滑动窗口
- 参考文献
1.问题描述
给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。
s 由英文字母、数字、符号和空格组成。
示例 1：
代码语言：javascript复制输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。示例 2：
代码语言：javascript复制输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。示例 3：
代码语言：javascript复制输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。2.难度等级
Medium。
3.热门指数
★★★★★
出题公司：阿里、腾讯、字节。
4.解题思路
方法一：暴力法
我们可以遍历字符串的所有字符，计算每个字符为起点的不含有重复字符的字串长度，记录到全局变量。
以示例 1 中的字符串 “abcabcbb” 为例，演示暴力法的求解过程。
代码语言：javascript复制以 (a)bcabcbb 开始的最长字符串为 (abc)abcbb
以 a(b)cabcbb 开始的最长字符串为 a(bca)bcbb
以 ab(c)abcbb 开始的最长字符串为 ab(cab)cbb
以 abc(a)bcbb 开始的最长字符串为 abc(abc)bb
以 abca(b)cbb 开始的最长字符串为 abca(bc)bb
以 abcab(c)bb 开始的最长字符串为 abcab(cb)b
以 abcabc(b)b 开始的最长字符串为 abcabc(b)b
以 abcabcb(b) 开始的最长字符串为 abcabcb(b)
所以最长子串长度为 3。如何判断重复字符？
常用的数据结构为哈希集合（即 C 中的 std::unordered_set，Java 中的 HashSet，Python 中的 set, JavaScript 中的 Set 和 Golang 中的 map 等）。
时间复杂度：
，n 为字符串长度。
空间复杂度： 最好为 O(1)，最坏为 O(n)。
方法二：滑动窗口
暴力法的求解过程，实际上存在不必要的检查。
以示例 1 中的字符串 “abcabcbb” 为例，演示暴力法的求解过程可优化的地方。
代码语言：javascript复制以 (a)bcabcbb 开始的最长字符串为 (abc)abcbb
以 a(b)cabcbb 开始的最长字符串为 a(bca)bcbb
以 ab(c)abcbb 开始的最长字符串为 ab(cab)cbb
以 abc(a)bcbb 开始的最长字符串为 abc(abc)bb
下面这一步是没有必要的，因为以 b 开始的不重复子串 bc 在上一个不重复子串内，长度肯定小于上一个不重复子串。
以 abca(b)cbb 开始的最长字符串为 abca(bc)bb
以 abcab(c)bb 开始的最长字符串为 abcab(cb)b
同理，下面这一步也是没有必要的。
以 abcabc(b)b 开始的最长字符串为 abcabc(b)b
以 abcabcb(b) 开始的最长字符串为 abcabcb(b)在获取一个子串时，如果遇到了重复字符，那么获取下一个无重复字符的子串时，应该从重复字符的下一个字符开始。
将无重复字符的子串想象成一个滑动窗口，整个求解过程是移动滑动窗口的过程。
如何移动滑动窗口？
当出现重复字符时，我们只要把窗口内重复字符及其左边的元素移出就行了。
一直维持这样的窗口，直至窗口滑动到最后一个字符。记录最长的窗口长度，求出解！
时间复杂度： O(n)，n 为字符串长度。
空间复杂度： 最好为 O(1)，最坏为 O(n)。
下面以 Golang 为例，给出实现。
代码语言：javascript复制func lengthOfLongestSubstring(s string) int {
var longest int
m := make(map[rune]bool)
var left int
for _, c := range s {
for m[c] {
delete(m, rune(s[left]))
left
}
m[c] = true
if len(m) > longest {
longest = len(m)
}
}
return longest
}参考文献
3. 无重复字符的最长子串
