3. Longest Substring Without Repeating Characters-白红宇

3. Longest Substring Without Repeating Characters

阅读量：796 次

发布时间：2023-03-23

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

为了解决寻找最长子串而没有重复字符的问题，我们可以使用滑动窗口方法。这种方法在O(n)的时间复杂度和O(1)的空间复杂度下，能够高效地解决问题。

方法思路

滑动窗口技术：我们维护一个窗口，窗口内的字符是不重复的。当遇到重复字符时，调整窗口的左端指针，确保窗口内没有重复字符。

初始化指针：使用两个指针left和right，分别表示窗口的左端和右端。此外，current_start记录窗口的起始位置，max_len记录最长子串的长度。

遍历字符串：对于每个字符，检查它是否在当前窗口中。如果存在重复，调整左端指针到当前字符的下一个位置。然后计算当前窗口的长度，更新最长长度。

解决代码

class Solution:
    def lengthOfLongestSubstring(self, s):
        left = 0
        max_len = 0
        current_start = 0
        for right in range(len(s)):
            if s[right] in s[current_start:right]:
                current_start = right + 1
            current_window = right - current_start + 1
            if current_window > max_len:
                max_len = current_window
        return max_len

代码解释

初始化变量：left和max_len初始化为0，current_start也初始化为0。

遍历字符串：使用right指针遍历字符串中的每个字符。

检查重复字符：如果当前字符已经存在于窗口内，调整左端指针current_start到当前字符的位置+1。

更新窗口长度：计算当前窗口的长度，并与max_len比较，更新最长长度。

返回结果：遍历结束后，返回最长子串的长度。

这种方法确保了在每次遍历时，窗口内的字符都是唯一的，并且能够在O(n)时间复杂度内找到最长子串。

转载地址：http://saqfk.baihongyu.com/

你可能感兴趣的文章