LeetCode 第三题：无重复字符的最长子串 详解 【3/1000】

👤作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。

会一些的技术：数据分析、算法、SQL、大数据相关、python

欢迎加入社区：码上找工作

作者专栏每日更新：

LeetCode解锁1000题: 打怪升级之旅

python数据分析可视化：企业实战案例

备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级

在字符串处理问题中，力扣（LeetCode）题库中的“无重复字符的最长子串”是一个经典的问题。这个问题的目标是从给定的字符串中找到最长的不含有重复字符的子串。

问题描述

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

示例：

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

解题思路-哈希集合

算法步骤

1. 初始化：定义两个指针，一个哈希集合，和一个用于记录最长子串长度的变量。
2. 滑动窗口：用两个指针表示字符串中的某个子串（或窗口），随着遍历的进行，调整指针和窗口的大小。
3. 更新哈希集合：通过哈希集合来判断字符是否重复，并据此调整左指针。
4. 更新最长长度：每次窗口滑动时，更新不含重复字符的最长子串的长度。

时间复杂度

算法的时间复杂度为 O(n)，其中 n 是字符串的长度。在最坏的情况下，每个字符将被访问两次（由两个指针各一次）。

空间复杂度

空间复杂度为O(min(m,n))，其中 m 是字符集（字母表）的大小。这是因为哈希集合的大小取决于字符串的大小 n 和字符集的大小 m。

代码示例（Python）

def length_of_longest_substring(s: str) -> int:
    char_set = set()
    left = max_length = 0
    
    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_length = max(max_length, right - left + 1)
    
    return max_length
 
# 测试代码
input_string = "abcabcbb"
print(length_of_longest_substring(input_string))

代码解释

• 我们遍历输入字符串，使用两个指针 left 和 right 表示当前考虑的子串。
• 我们使用一个集合 char_set 来存储当前子串中的字符。
• 当我们碰到一个已经存在于集合中的字符时，我们就不断地移动左指针，并从集合中移除相应的字符，直到这个字符不再出现在集合中。
• 每次我们都会更新最大长度 max_length。

其他思路-字符集为数组

利用字符集为数组的方法特别适用于字符集大小固定且较小的情况，例如ASCII字符集。这种方法利用数组的索引来代表字符，数组的值来表示字符最后一次出现的位置。这样，我们可以在 O(1) 的时间内检查和更新每个字符的最后出现位置，从而在遍历字符串时快速判断当前字符是否重复，以及如何移动滑动窗口的起始位置。

代码示例

def length_of_longest_substring(s: str) -> int:
    # 初始化字符最后一次出现位置的数组，-1 表示字符尚未出现
    last_index = [-1] * 128  # ASCII 字符集大小为 128
    max_length = 0
    start = 0  # 滑动窗口的起始位置
    
    for i, char in enumerate(s):
        # 更新滑动窗口的起始位置
        # 如果当前字符之前出现过，则更新窗口起始位置为上一次出现位置 + 1
        if last_index[ord(char)] != -1:
            start = max(start, last_index[ord(char)] + 1)
        
        # 更新当前字符的最后出现位置
        last_index[ord(char)] = i
        
        # 计算当前无重复字符子串的长度，并更新最大长度
        max_length = max(max_length, i - start + 1)
    
    return max_length
 
# 测试代码
input_string = "abcabcbb"
print(length_of_longest_substring(input_string))

这段代码首先初始化一个长度为128的数组last_index来存储每个ASCII字符最后一次出现的索引位置，初始值为-1表示字符未出现。随后遍历字符串，使用ord(char)获取字符的ASCII值作为索引，通过last_index数组来快速查找字符最后一次出现的位置，并据此更新滑动窗口的起始位置start。最终，通过比较每个字符对应的无重复字符子串长度来得到最大值。

算法对比

1. 时间复杂度：这个方法仍然保持 O(n) 的时间复杂度，与基于哈希集合的滑动窗口方法相同。
2. 空间复杂度：当字符集大小固定且较小时（比如ASCII字符集），这种方法的空间复杂度实际上是 O(1)，相较于哈希集合方法（在最坏情况下可能接近 O(n)，尽管实际使用中较少达到这个上限）更优。
3. 操作复杂度：使用数组直接访问和更新字符的最后一次出现位置，操作更为直接和高效，特别是在字符集较小的情况下。

因此，如果你确定字符集的大小是固定和有限的，利用字符集为数组的方法在理论上是更优的选择，尤其是在空间复杂度上。然而，这种方法的优势主要体现在处理小字符集的字符串上，例如ASCII字符集。

但是，如果问题涉及到更大的字符集，比如Unicode字符集，哈希集合的方法可能更加灵活和通用，因为它不受字符编码范围的限制。同时，哈希集合方法的代码通常更简洁、易于理解和维护，特别是对于那些对特定编码方式不太熟悉的开发者。

欢迎关注微信公众号 数据分析螺丝钉