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

为解决给定一个字符串中找最长子串的重复字符问题，以下方法可以有效地实现：

方法思路

我们可以使用哈希表来记录每个字符最后出现的位置。遍历字符串时，对于每个字符，如果它已经在当前窗口中出现过，则调整窗口的起始位置，以确保没有重复字符。具体步骤如下：

这种方法的时间复杂度为 O(n)，其中 n 是字符串的长度，空间复杂度为 O(1)，因为哈希表的大小是固定的（根据字符集的大小）。

代码实现

def lengthOfLongestSubstring(s):
    last = {}
    max_len = 0
    left = 0
    for i, char in enumerate(s):
        if char in last:
            # 如果字符已经存在，更新left为该字符上一次出现的位置+1
            left = max(left, last[char] + 1)
        # 记录当前字符的位置
        last[char] = i
        # 计算当前窗口长度
        current_len = i - left + 1
        if current_len > max_len:
            max_len = current_len
    return max_len

解释

通过使用哈希表跟踪字符位置，算法可以在每次遇到重复字符时快速调整窗口起始位置，以确保在当前窗口内没有重复字符。这种方法高效且直接，能够在一次遍历中找到最长子串，性能优异。

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