网站系统管理,网站建设后如何放在网上,现代简约风格设计方案ppt,最好的网站模板网站文章目录 1.问题描述2.难度等级3.热门指数4.解题思路方法一#xff1a;暴力法方法二#xff1a;滑动窗口 参考文献 1.问题描述
给定一个字符串 s #xff0c;请你找出其中不含有重复字符的最长子串的长度。
s 由英文字母、数字、符号和空格组成。
示例 1#xff1a;
输… 文章目录 1.问题描述2.难度等级3.热门指数4.解题思路方法一暴力法方法二滑动窗口 参考文献 1.问题描述
给定一个字符串 s 请你找出其中不含有重复字符的最长子串的长度。
s 由英文字母、数字、符号和空格组成。
示例 1
输入: s abcabcbb
输出: 3
解释: 因为无重复字符的最长子串是 abc所以其长度为 3。示例 2
输入: s bbbbb
输出: 1
解释: 因为无重复字符的最长子串是 b所以其长度为 1。示例 3
输入: s pwwkew
输出: 3
解释: 因为无重复字符的最长子串是 wke所以其长度为 3。2.难度等级
Medium。
3.热门指数
★★★★★
出题公司阿里、腾讯、字节。
4.解题思路
方法一暴力法
我们可以遍历字符串的所有字符计算每个字符为起点的不含有重复字符的字串长度记录到全局变量。
以示例 1 中的字符串 “abcabcbb” 为例演示暴力法的求解过程。
以 (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_setJava 中的 HashSetPython 中的 set, JavaScript 中的 Set 和 Golang 中的 map 等。
时间复杂度 O ( n 2 ) O(n^2) O(n2)n 为字符串长度。
空间复杂度 最好为 O(1)最坏为 O(n)。
方法二滑动窗口
暴力法的求解过程实际上存在不必要的检查。
以示例 1 中的字符串 “abcabcbb” 为例演示暴力法的求解过程可优化的地方。
以 (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 为例给出实现。
func lengthOfLongestSubstring(s string) int {var longest intm : make(map[rune]bool)var left intfor _, c : range s {for m[c] {delete(m, rune(s[left]))left}m[c] trueif len(m) longest {longest len(m)}}return longest
}参考文献
3. 无重复字符的最长子串
