无重复字符的最长子串习题分析

习题：（leetcode 3 ）

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

分析：

对于寻找子串、数组中某部分等，我们可以使用滑动窗口和双指针思想来求解。

滑动窗口通常用于解决需要连续子数组/子串的问题。

滑动窗口：

滑动窗口是一种抽象的概念，它表示一个在数组/字符串中滑动的窗口。这个窗口可以扩张或收缩，以解决问题。滑动窗口通常用于寻找数组/字符串的特定子集（例如，最长/最短子串或子数组）。

滑动窗口的基本步骤如下：

1.初始化两个指针，通常称为 left 和 right，它们分别表示窗口的左右边界。

2.扩张 right 指针以包含更多的元素。

3.当窗口满足某些条件时，收缩 left 指针以排除一些元素。

4.重复步骤 2 和 3，直到 right 指针到达数组的末尾。

思路：

通过set进行存放插入的元素，通过right进行向右遍历，因为set机制，当set.count()中是已经包含的数则输出1，不包含就输出0。

当有相同的字符出现时，set.insert()停止插入字符，通过left开始向前遍历，而循环依次按照set.earse()进行删除直到set中不在存放着与right指向相同的字符。因没有与right指向字符相同的，所以跳出循环，再将right指针指向的字符加入set，然后以此类推。直到right走到末尾。

代码分析：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // 初始化左右指针，用于表示当前子串的边界
        int left = 0, right = 0;
        // 初始化当前子串长度和最长子串长度
        int length = 0, maxLength = 0;
        // 使用unordered_set来存储当前子串中的字符，确保字符唯一性
        unordered_set<char> set;

        // 遍历字符串，直到右指针到达字符串末尾
        while (right < s.length()) {
            // 如果当前字符不在set中，说明它是新的字符，可以添加到当前子串
            if (!set.count(s[right])) {
                set.insert(s[right]); // 将字符添加到set中
                length++; // 增加当前子串长度
                // 如果当前子串长度大于已知最长子串长度，更新最长子串长度
                if (length > maxLength) {
                    maxLength = length;
                }
                right++; // 移动右指针，扩展子串
            } else {
                // 如果当前字符已经在set中，说明出现了重复字符
                // 需要移动左指针，缩小子串范围，直到重复字符被移除
                while (set.count(s[right])) {
                    set.erase(s[left]); // 从set中移除左指针指向的字符
                    left++; // 移动左指针，缩小子串范围
                    length--; // 减少当前子串长度
                }
                // 将当前右指针指向的字符添加到set中
                set.insert(s[right]);
                length++; // 增加当前子串长度
                right++; // 移动右指针，扩展子串
            }
        }
        // 返回最长子串的长度
        return maxLength;
    }
};