LeetCode ＃3.无重复字符的最长子串

力扣 | 3.无重复字符的最长子串

题目截图

方法一：暴力法

利用列表。利用列表切片来滑动窗口。

遍历字符串s，不断将字符串的字符添加到列表中。

如果发现字符串中新的元素在前面的列表中有，立刻使用切片，使切片的开头切在重复元素的后一位，然后添加那个重复的元素（此时已经把重复的部分切掉了），再继续往下遍历。

每一次添加都比较长度，选择长度大的那个，最后返回最大子串长度。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        a = []
        res = 0
        for i in s:
            if i in a:
                a = a[a.index(i)+1:]
            a.append(i)
            res=res if len(a)< res else len(a)
        return res

res可以直接用max()函数

res = max(res, len(a))

完整测试代码

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        a = []
        res = 0
        for i in s:
            if i in a:
                a = a[a.index(i)+1:]
            a.append(i)
            res=res if len(a)< res else len(a)
        return res

class main():
    a = Solution()
    s = "abcabcbb"
    print(a.lengthOfLongestSubstring(s))

if __name__ == '__main__':
    main()

方法二：滑动窗口一

set()函数可以创建一个不重复的元素集，可以利用该函数判断是否有重复的部分。

Python set() 函数 | 菜鸟教程

内循环判断新添加的元素是否重复，如果不重复则指针右移，将其加入元素集。如果新加入的元素重复在无法进入循环，跳出循环后进外循环，外循环会删除掉前面的元素，该元素为之前重复的元素。

这样利用左右指针滑动窗口可以找到一系列子字符串，利用max()函数返回无重复最大子字符串。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 哈希集合，记录每个字符是否出现过
        occ = set()
        n = len(s)
        rk, ans = -1, 0
        for i in range(n):
            if i != 0:
                occ.remove(s[i - 1])
            while rk + 1 < n and s[rk + 1] not in occ:
                occ.add(s[rk + 1])
                rk += 1
            ans = max(ans, rk - i + 1)
        return ans

方法三：滑动窗口二

基本思路与上面相同有一点点区别。更容易看懂一点。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        occ = set()
        left = 0
        max_len, cur_len = 0, 0
        n = len(s)
        for i in range(n):
            cur_len += 1
            while s[i] in occ:
                occ.remove(s[left])
                left += 1
                cur_len -= 1
            max_len = max(max_len, cur_len)
            occ.add(s[i])
        return max_len