leetcode - 无重复字符的最长子串

leetcode: 无重复字符的最长子串

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

这个问题首先我们可以想到的就是暴力破解，（依稀记得以前一个数学老师的三大鬼才解法，暴力破解，数学归纳，容易证得= =），但是暴力破解就就要把所有情况考虑进去，我们可以算一下时间复杂度

设一长度为n的字符串，当考虑答案为n的情况就需要n^2的时间，然后一共有1 + 2 + 3 + 4…..n-1种情况，那么最坏要达到n^3以上的复杂度，所以我们最好不要用暴力破解

我们就采用了一种滑动窗口方法，故名思义，滑动窗口就是一个左右边界不确定变长的串，代码如下

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        l = []                                //滑动窗口
        count = 0                             //最长串长度
        Ncount = 0                            //现在串的长度
        left = 0                              //窗口左边位置
        right = 0                             //窗口右边位置
        for i in range(len(s)):               //遍历字符串
            Ncount+= 1                        //每加一个字符，长度加一
            while s[i] in l:                  //检查是否有重复
                l.remove(s[left])             //左窗口不断右滑直到没有重复字符
                left += 1
                Ncount -= 1
            if Ncount > count:
                count = Ncount
            l.append(s[i])
        return count

实际上，滑动窗口在计算机网络信息传递时有很重要的作用，这一题可以辅助学习

嘛~

今天的leetcode就这样了，晚点要是做完了做一期B样条曲线

啊，不想上晚课啊艹