使用双指针滑动窗口解决最长无重复子串问题

简介：在本篇博客中，我们将探讨如何使用双指针滑动窗口方法解决一个常见的字符串问题：找到给定字符串中最长无重复字符的子串长度。我们将介绍两个解决方案：通用模板版本和优化版本。

问题描述：给定一个字符串，找到其中最长的无重复字符的子串。返回其长度。

示例：
输入：s = "abcabcbb" 
输出：3 
解释：最长无重复子串为 "abc"，长度为 3。

解法1：双指针滑动窗口通用版本

在这个解法中，我们使用双指针滑动窗口方法，同时维护一个列表str_list来存储窗口内的字符。快指针（right）遍历整个字符串，慢指针（left）始终在快指针的左侧。

当遇到新字符时，将其添加到str_list中；当遇到重复字符时，将慢指针所指字符从str_list中移除，并将慢指针向右移动。在遍历过程中，我们不断更新最长无重复子串的长度。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        str_list = []
        left, right, res = 0, 0, 0

        while right < len(s):
            current_str = s[right]
            if current_str not in str_list:
                str_list.append(current_str)
                right += 1
                res = max(res, right - left)
            else:
                str_list.remove(s[left])
                left += 1
        return res

解法2：优化版本

在优化版本中，我们使用一个字典str_dict来存储每个字符最近出现的位置。遍历字符串时，若当前字符已经在字典中，我们更新慢指针的位置。同时，我们使用一个变量res来记录最长无重复子串的长度。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        res, left, str_dict = 0, 0, {}

        for index, value in enumerate(s):
            if value in str_dict:
                left = max(left, str_dict[value])
            res = max(res, index - left + 1)
            str_dict[value] = index + 1
        return res

总结：

在本篇博客中，我们学习了如何使用双指针滑动窗口方法解决最长无重复子串问题。这种方法在解决其他类似的字符串或数组问题时也非常有用。通过优化数据结构和遍历策略，我们可以进一步提高算法的效率。