LeetCode 03 无重复字符的最长子串（python3）

字符串的子串求解类问题是一整个系列的方法，正好用这道题作为我个人学习的一个总结吧。
作为一个没有训练过特定解法的新手，能够想到的最直观方法应该就是暴力求解法，这个方法时间复杂度必然很高，但是好在思路清晰，也容易上手，所以就先从暴力法开始吧。

题目描述：

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

示例 1:

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

示例 2

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

示例 3:

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

暴力求解法

• 我的初始思路：
  维护一个子串sub_string，外层循环按照给定字符串s每一个字符顺序扫描，并且和子串每一个字符进行比较（这里子串扫描应该从后往前），一旦当前字符在子串中找到相同的字符，那么子串就从相同字符前一个那里截断，然后把新字符加在结尾。每轮扫描后更新最长子串的长度，循环结束后返回。

• 代码：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        sub_string = ''
        lens = 0
        for i in range(len(s)):
            if sub_string:
                for j in range(len(sub_string)-1,-1,-1):
                    if s[i] == sub_string[j]:
                        sub_string = sub_string[j+1:]
                        break
            sub_string+=s[i]
            #print(sub_string)
            lens = max(lens, len(sub_string))
        return lens

• 结果：
  因为两层嵌套循环的使用，结果时间复杂度约为O（n^2），那么速度也是可想而知的慢……（还好没超时）

执行用时 :372 ms, 在所有 python3 提交中击败了13.76%的用户

我这个速度是注定要被人嘲笑的（还好我脸皮厚），接下来就是进阶之路啦。

暴力求解法的进化思路 -- 滑块法

• 思路：
  我在网上偶然发现了一个跟我的思路非常像，但是效率高了很多的解法。来自于简书冬小羊的这篇博客，可以去读一下。
  这个解法优化的点在于：

1. 不需要维护一个子串了，而采用哈希表的方式记录每一个字符出现的次数，这样就可以很方便的找到多余的字符。

2. 同时也就不需要遍历子串找到截断点。而是采用双指针指向子串首尾的方式，一旦子串里有字符重复，那么就移动子串头一格，直到子串里没有重复字符为止。其实这一步做的事情就相当于截断子串了。
   

   下面这张图也来自于冬小羊的博客，大家可以直观感受一下这个解法： 滑动法图解

• 代码：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        start = 0 # 子串起点指针
        end = 0 # 子串终点指针
        char_dict = dict() #统计子串中每一个字符出现的个数
        lens = 0

        for i in s:
            end += 1
            char_dict[i] = char_dict.get(i,0)+1
            while char_dict[i] > 1:
                char_dict[s[start]] -= 1
                start += 1
            lens = max(lens,end-start)
        return lens

• 结果：
  不得不说，这样修改之后，效果真的是杠杠的

执行用时 :80 ms, 在所有 python3 提交中击败了78.88%的用户

因为这样其实只有一个循环，内层因为巧妙使用指针和哈希表（就是字典表）所以大大提升了运行效率，感谢网友朋友们的智慧。