双指针 8 （无重复字符的最长子串 leetcode 3）
2023-02-06 本文已影响0人
Sisyphus235
思想
双指针算法不仅应用于链表，在数组等数据结构中也有广泛应用。
核心思路是指向问题中的关键节点，根据问题的上下文逻辑变换位置，最终解决问题。
实例
无重复字符的最长子串 leetcode 3
输入：
s: str，一个字符串；
输出：
int，不含有重复字符的最长子串的长度。
举例：
当输入 "abcabcbb" 时，最长的无重复字符子串是"abc"，返回长度 3。
关键点
这里的关键点是子串的开始位置，和子串能否扩展的尾部，如果当前不重复，则尾部向后扩展。
难点是如果重复，如何高效的找到下面一个不重复子串的开头，最低效的方式是子串开头向后移动一位，这时就必须也要将尾部重置到当前头结点的位置。
高效的方式是在当前子串扩展的过程中有记录信息，当扩展遇到重复字母时能找到上一个相同字母的位置，这样新的子串其实位置就在这个位置的下一个。接着清理掉从旧的子串起点到新的起点之间的元素记录。
"abcabcbb" 为例
start=a, end=b，记录 {a:0, b:1}
start=a, end=c，记录 {a:0, b:1, c:2}
start=a, end=a，重复，记录中 a 的位置是 0，当前子串长度 3，记录更新为 {a:3, b:1, c:2}，新子串起点在 1
start=b, end=b，重复，记录中 b 的位置是 1，当前子串长度 3，记录更新为 {a:3, b:4, c:2}，新子串起点在 2
start=c, end=c，...
最终返回最大长度 3
编码
# -*- coding: utf8 -*-
def longest_substring_without_repeating_characters(s: str) -> int:
# 边界保护
if len(s) <= 1:
return len(s)
# 初始化，申请一块不重复元素的 index 记录内存
char_dict= {s[0]: 0}
max_len = 0
start, end = 0, 1
# 遍历
while end < len(s):
if s[end] in char_dict:
max_len = max(max_len, end - start)
# 下一个子串开头在当前重复元素所在位置的下一个
for i in range(start, char_dict[s[end]]):
char_dict.pop(s[i])
start = char_dict[s[end]] + 1
# 重复则更新不重复元素的下标，不重复则增加不重复元素信息
char_dict[s[end]] = end
end += 1
max_len = max(max_len, end - start)
return max_len
