python 无重复字符的最长子串多种解法

编程小白狼

发布于 2024-12-31 08:09:51

3640

暴力枚举法：枚举所有可能的子串并检查它们是否有重复的字符。时间复杂度为 O(n3)。
滑动窗口法：维护一个滑动窗口，该窗口包含的子串没有重复的字符。我们向右移动窗口，并在每个位置更新最长的无重复子串。时间复杂度为O(n)。

代码如下：

def lengthOfLongestSubstring(s: str) -> int:
    n = len(s)
    ans = 0
    i, j = 0, 0
    lookup = set()
    while i < n and j < n:
        if s[j] not in lookup:
            lookup.add(s[j])
            j += 1
            ans = max(ans, j - i)
        else:
            lookup.remove(s[i])
            i += 1
    return ans

哈希表法：使用哈希表来存储每个字符最后出现的位置。然后，我们可以使用两个指针来维护一个窗口。右指针 j 用于扩展当前窗口，而左指针 i 用于排除不在窗口中的旧字符。时间复杂度为O(n)。

代码如下：

def lengthOfLongestSubstring(s: str) -> int:
    n = len(s)
    ans = 0
    lookup = {}
    i = 0
    for j in range(n):
        if s[j] in lookup:
            i = max(lookup[s[j]], i)
        ans = max(ans, j - i + 1)
        lookup[s[j]] = j + 1
    return ans

无论使用哪种算法，它们的时间复杂度都为O(n)，其中 n 是字符串的长度。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-12-09，如有侵权请联系 cloudcommunity@tencent.com 删除

指针