【leetcode刷题】20T3-无重复字符的最长子串

• 2020 年 2 月 16 日
• 笔记

木又同学2020年第3篇解题报告

leetcode第3题：无重复字符的最长子串

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

【题目】

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:  输入: "abcabcbb"  输出: 3  解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。    示例 2:  输入: "bbbbb"  输出: 1  解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。    示例 3:  输入: "pwwkew"  输出: 3  解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。       请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。  

【思路】

可以暴力求解，对于每一个子串，判断是否有重复字符。判断是否有重复字符，需要O(n)，所以总的时间复杂度为O(n^3)

我们想想，有很多子串是没有必要判断的，比如对于"dvdf"，当知道“dvd”是重复子串时，“dvdf”肯定是重复子串。因此，我们使用i表示非重复子串起始下标，j用于遍历数组，当s[j]存在于s[i:j]中，说明s[i:j+1]是重复子串，s[i:j]是以i为起点的最长非重复子串，然后更改i为s[i:j]中与s[j]相同的元素的下标。

【代码】

python版本

class Solution(object):      def lengthOfLongestSubstring(self, s):          """          :type s: str          :rtype: int          """          # 窗口i->j          i = 0          res = 0          for j in range(i+1, len(s)):              # 如果有重复字符，比较res和前一段非重复字符串长度，并更改i              if s[j] in s[i:j]:                  res = max(res, j-i)                  i += s[i:j].index(s[j]) + 1          # 不要忘了，最后要比较res和len(s)-i          res = max(res, len(s)-i)          return res  

C++版本

class Solution {  public:      int lengthOfLongestSubstring(string s) {          int i = 0;          int res = 0;          for (int j=i+1; j < s.size(); j++){              // s[i:j]中是否存在s[j]              // 存在比较长度，且更新i              int offset = s.substr(i, j-i).find(s[j]);              if (offset >= 0){                  res = max(res, j-i);                  i += offset + 1;              }          }          // 不要忽略最后一段子串          int tmp = s.size() - i;          res = max(res, tmp);          return res;      }  };