本文共 1316 字，大约阅读时间需要 4 分钟。

makcooo 2019-04-19 15:47:32  271  收藏

分类专栏： python 版权 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: “abcabcbb”

输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。 示例 2:

输入: “bbbbb”

输出: 1 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。 示例 3:

输入: “pwwkew”

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

 

class Solution:    def lengthOfLongestSubstring(self, s):        """        :type s: str        :rtype: int        """        st = {}#建立一个空字典        i, ans = -1, 0        for j in range(len(s)):            if s[j] in st:                i = max(st[s[j]], i) #i是目前正在计算的最长字串的起点位置            ans = max(ans, j - i )""" j 表示子串终止位置，i表示字串起始位置 当未出现重复时，字符串的长度即为字符串的结束位置减去起始位置。发生重复时，重新利用字符串的结束位置j减去新的起始位置i，并与之前的未重复字串的长度作比较取较大者"""            st[s[j]] = j  #输入 s[j] ：j        return ans;

 

原理：使用哈希表存储键值对（key：字符，value：该字符最后一次出现的后一个位置），遍历字符串，若当前字符在哈希表中，则到当前字符为止的最大不重复子串开始位置为“哈希表中该字符的 value 与原开始位置的最大值”，总的最大长度为“原最大长度与当前字符最大长度的最大值”，最后将当前字符的哈希表值更新。

上面是一个滑动窗口的思想，将新的数据与已有的相比较，从索引 i到 j−1 之间的子字符串 s​ 已经被检查为没有重复字符。我们只需要检查 s[j] 对应的字符是否已经存在于子字符串 s中即可

滑动窗口是数组/字符串问题中常用的抽象概念。 窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合，即 [i, j)（左闭，右开）。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如，我们将 [i, j) 向右滑动 1 个元素，则它将变为 [i+1, j+1)（左闭，右开）。

———————————————— 版权声明：本文为CSDN博主「makcooo」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/qq_44756223/article/details/89401804