Loading... # [无重复字符的最长子串](https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/description/) | Category | Difficulty | Likes | Dislikes | | :-: | :-: | :-: | :-: | | algorithms | Medium (34.87%) | 3872 | - | 给定一个字符串,请你找出其中不含有重复字符的 **最长子串** 的长度。 **示例 1:** ``` 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。 ``` **示例 2:** ``` 输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。 ``` **示例 3:** ``` 输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。 请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。 ``` --- [Discussion](https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/comments/) | [Solution](https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/) ## 读题 从给定字符串中查找不重复的最长子字符串的最大长度 ### 反面教材 正如读题所说,那就暴力遍历所有子串判断排除重复项最后取最长的吧 ```c# public class Solution { public int LengthOfLongestSubstring(string s) { string nowStr = ""; int maxRes = 0; //遍历字符 for (int startIndex = 0; startIndex < s.Length; startIndex++) { int lengthMax = s.Length - startIndex; //遍历每个char开头的所有长度的字符串 for (int i = 1; i <= lengthMax; i++) { //小于当前最长的可以不遍历 if (i <= maxRes) { continue; } //当前字符串 nowStr = s.Substring(startIndex, i); bool repeat = isRepeat(nowStr); if (!repeat) { //没有重复,记录长度 maxRes = nowStr.Length; } } } return maxRes; } public bool isRepeat(string s) { //计算字符串中所有字符的索引,第一个索引和最后一个索引值不一样表示有重复 foreach (var item in s) { int fstIndex = s.IndexOf(item); int lastIndex = s.LastIndexOf(item); if (fstIndex != lastIndex) { return true; } } return false; } } ``` <div class="tip inlineBlock error"> 这里是个反面教材,缺乏思考偷懒只会增加加班时长! ***无脑遍历,时间复杂度太高,对于输入值过长且复杂的情况,性能严重下降*** 反例:当给定字符串非常长非常爆炸的时候,执行时间也非常爆炸! 时间复杂度: O(n^n^n)【要查找长度为n的字符串中的所有子串,每个子串还要遍历每个字符检查是否重复,极其爆炸】 </div> ### 优化策略 用正常人类思维考虑程序问题: abcbda如何判断结果是cbda,长度为4呢? - 从头开始数,不重复的话,记录长度 此时我们数到"abc"=3 - 遇到重复"b" 两个"b"之间的字母肯定不重复,那我们取出来,再拼上末尾的"b" 得到"c"+"b"="cb" - 得到的"cb"有没有破纪录呢? "cb"=2 最大是3,没有破纪录,那还是3 - 继续数,上次到第二个"b",该"d"了 重复1234,最后得到"cbda"=4 4>3,破纪录了,记录为4 - 数完啦! 最后的记录是4! ***卧槽!人脑实在是太聪明了*** --- 这就是传说中的,滑动窗口算法! ## 正确解法 ```c# public class Solution { public int LengthOfLongestSubstring(string s) { //特殊处理,空字符串直接返回 if (string.IsNullOrEmpty(s)) { return 0; } //非空字符串最小返回值也是1 int maxRes = 1; //当前窗口 List<char> nowWindow = new List<char>(); foreach (var nowChar in s) { //遍历字符串的每个字符,窗口中存在,则抛弃前一个字符以前的所有 //如 字符串abcb 当前abc 遇到第2个b 则窗口abc->c(去掉b及b以前的所有) if (nowWindow.Contains(nowChar)) { nowWindow.RemoveRange(0, nowWindow.IndexOf(nowChar) + 1); } //再加上b到末尾成为窗口成为cb nowWindow.Add(nowChar); //当前窗口是否大于历史最大尺寸,大于则刷新纪录 if (nowWindow.Count > maxRes) { maxRes = nowWindow.Count; } } return maxRes; } } ``` ### 结果 - 987/987 cases passed (92 ms) - Your runtime beats 93.12 % of csharp submissions - Your memory usage beats 40 % of csharp submissions (25 MB) ### 思考 - 可以看到速度很快,空间占用还是不如人意。 - 可否使用Dictionary 利用key不重复的结构特性实现优化? - 空间占用不行是因为使用了List,可否通过记录窗口起始index及结束index,计算子串重复更改窗口始末index位置仅使用几个int记录索引完成计算,从而减少空间占用呢? ### 膜拜大佬 如果大佬们有更好的解法,不如评论分享赐教~ [我的Leetcode解题代码库][1] [1]: https://github.com/traceless0929/.leetcode Last modification:July © Allow specification reprint Support Appreciate the author AliPayWeChat Like 0 如果觉得我的文章对你有用,请随意赞赏