思想

双指针算法不仅应用于链表，在数组等数据结构中也有广泛应用。
核心思路是指向问题中的关键节点，根据问题的上下文逻辑变换位置，最终解决问题。

实例

无重复字符的最长子串 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

相关

双指针 0
双指针 1
双指针 2
双指针 3
双指针 4
双指针 5
双指针 6
双指针 7