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

来源:3-8 在滑动窗口中做记录 Longest Substring Without Repeating Characters

stcheng1982

2017-09-18

老师的示例代码中 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 下标是否到边来控制循环结束。

谢谢

写回答

1回答

liuyubobobo

2017-09-18

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


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

1
2
stcheng1982
使用左下标的意义我有点明白了 包括r到达边界后不退出 这样可以覆盖到所有substring 取值 我再体会一下 非常感谢
2017-09-18
共2条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题,高频算法题解析,强化训练

7408 学习 · 1150 问题

查看课程