题目

3. 无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:

  1. 输入: s = "abcabcbb"
  2. 输出: 3 
  3. 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

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

示例 4:

输入: s = ""
输出: 0

提示：

  • 0 <= s.length <= 5 * 104
  • s 由英文字母、数字、符号和空格组成

题解

最初始的想法是：

  1. 左指针从0位置开始
  2. 从左指针开始往右，找到最长的无重复子串

  3. 然后左指针+1，继续寻找

    class Solution:
 def lengthOfLongestSubstring(self, s):
     max_len=0
     if s=='':
         return 0
     for left in range(len(s)):
         for right in range(left,len(s)):
             if s[right] in s[left:right]:
                 break
             max_len=max(max_len,right-left+1)
     return max_len

    时间复杂度

    但是花了3952 ms，大概处于最后5%，说明算法有待改进。
    时间复杂度为 3. 无重复字符的最长子串 - 图1，其中n为字符串长度，m为所有字符的数目。

    优化

    改进也很简单，因为 s[left:right] 都是无重复的，所以当 left 右移一位时， s[left+1:right] 自然还是无重复的，所以right不用再从left开始遍历，继续从上一次的letf处开始即可。
    然后看了其他人的解法，还有两个可以优化的地方：

  4. 在判断字符有没有在字符串中时，可以用hash表来储存，但由于无重复的字符串长度最大也就100左右，因此差异几乎可以忽略不计

  5. 当 max_len > n-left-1 时，可以提前终止
    class Solution:
 def lengthOfLongestSubstring(self, s):
     n = len(s)
     max_len = 0
     right = 0
     occ = set()
     for left in range(n):
         while right < n and s[right] not in occ:
             occ.add(s[right])
             right += 1
             max_len = max(max_len, right-left)
         occ.remove(s[left])
         if max_len > n-left-1:
             break
     return max_len
    新方法的时间复杂度为 3. 无重复字符的最长子串 - 图2