### Python 中获取不重复子串的算法 在 Python 中，可以通过滑动窗口技术来高效地解决无重复最长子串问题。这种方法的时间复杂度为 O(n)，相较于暴力解法更加优化。 以下是基于滑动窗口方法的一个具体实现： #### 实现代码 ```python def length_of_longest_substring(s: str) -> int: char_index_map = {} # 字符到索引的映射表 max_length = 0 # 记录最大长度 start = 0 # 当前窗口起始位置 for i, char in enumerate(s): if char in char_index_map and char_index_map[char] >= start: start = char_index_map[char] + 1 char_index_map[char] = i current_window_length = i - start + 1 max_length = max(max_length, current_window_length) return max_length ``` 上述代码的核心逻辑在于维护一个动态调整的窗口范围 `start` 到当前字符的位置 `i`，并利用哈希表记录每个字符最近一次出现的位置[^4]。 如果发现某个字符已经存在于当前窗口范围内，则更新窗口起点至该字符上一次出现位置之后的第一个位置，从而确保窗口内的所有字符均唯一。 --- #### 示例运行 对于输入字符串 `"abcabcbb"`，执行过程如下： - 初始化：`char_index_map = {}`, `max_length = 0`, `start = 0` - 遍历第一个 `'a'` (`i=0`)：加入哈希表 `{ 'a': 0 }`，计算窗口长度为 1。 - 遍历第二个 `'b'` (`i=1`)：加入哈希表 `{ 'a': 0, 'b': 1 }`，计算窗口长度为 2。 - 遍历第三个 `'c'` (`i=2`)：加入哈希表 `{ 'a': 0, 'b': 1, 'c': 2 }`，计算窗口长度为 3。 - 遍历第四个 `'a'` (`i=3`)：检测到冲突，更新窗口起点为 `start = 1`，重新计算窗口长度为 3。 最终返回的最大长度为 3，对应子串为 `"abc"`。 --- #### 关键点解析 1. **滑动窗口的作用**：通过两个指针（`start` 和 `i`），可以有效地控制窗口大小，并实时更新最大值。 2. **哈希表的功能**：用于快速查询某字符是否已经在当前窗口中存在及其最后一次出现的位置。 3. **时间复杂度分析**：由于每个字符最多被访问两次（进入和移除窗口各一次），因此整体时间为线性级别 \(O(n)\)[^4]。 ---