3-8 滑动窗口 Longest Substring Without Repeating Characters代码中的疑问

Question

老师的示例代码中 r 下标会先判断是否超出数组长度，但是一旦超出会转而去增加l下标。我的理解是一旦r到达边界（r+1超出)是循环已经可以退出，因为不会再有更长的substring了。而且r+1超出时，如果转而去增加l ，后面还会去做一次 res=max（res， r-l+1）， 这个似乎是多余的，而且逻辑上也不对（虽然不会影响最终结果)

我是这样实现的：

class Solution(object):
    def lengthOfLongestSubstring(self, s):
      
        if not s or len(s) ==0:
            return 0
        
        l=0
        r=-1
        ssize = len(s)
        charmap = [0 for i in range(128)]
        maxlen = 0
        while l<ssize:
            if r+1 >= ssize:
                break
            if charmap[ord(s[r+1])]==0:
                charmap[ord(s[r+1])]+=1
                r+=1                
                maxlen = max(maxlen, r-l+1)
            else:
                while l<ssize and charmap[ord(s[r+1])]>0:
                    charmap[ord(s[l])]-=1
                    l+=1
        return maxlen

顺便问一下对于滑动窗口的迭代，老师似乎都喜欢用左下标l 来作为循环判断条件，这个是有什么好处么（比如边界处理), 我一般习惯于用r 下标是否到边来控制循环结束。

谢谢

Answer 1

liuyubobobo 2017-09-18 12:35:40

我没有仔细看你的代码，但看了你的叙述，你的思路是没有问题的。因为这个问题是求解窗口长度最长的解，所以确实在r到达边界以后就不会有新的更优解了。但是我没有理解为什么做res=max（res， r-l+1）“逻辑上也不对”？

使用左下标来判断，是因为这样其实才真正将所有的窗口都遍历了一遍。我们从初始的一个空窗口出发，经过循环迭代以后，到最终回归到了一个空窗口。在有些问题中，如果我们最优化的内容不是窗口的长度，而是窗口中的元素的某些性质的话，我们需要保证能够遍历到所有可能的窗口：）

• 提问者 stcheng1982 #1

  后面半段是我自己理解错了 示例代码里 l增加时逻辑是对的 因为那时候r没有增加到重复的位置 只是做了多余的 max 比较。抱歉

• 提问者 stcheng1982 #2

  使用左下标的意义我有点明白了 包括r到达边界后不退出 这样可以覆盖到所有substring 取值 我再体会一下 非常感谢