环球看热讯：3 无重复字符的最长子串
发布时间：2023-05-27 23:53:12
来源：哔哩哔哩
无重复字符的最长子串
方法一：哈希表
使用哈希表，以键值对的方式存储 （单字符，该字符位序）。一次遍历，不重复则存入哈希表并且使用滑动数组更新最大长度，否则读取第一次出现的下标,从该位置的下一个位序继续遍历，并且清空整个哈希表；
Python版本
C++版本
复杂度分析
时间复杂度：O(N)。此处的 n指的是字符数组 s的长度。
【资料图】
空间复杂度：O(C)。字母最多有 26种，因此最大非重复子串的长度为26。
方法一：滑动窗口
分别初始化左右指针，右指针初始化为-1，左指针为0；内部while循环枚举不重复字符串，for循环枚举重复时，应当去除的左边界字符，每当遇到重复字母时，更新最大长度。
Python版本
C++版本
复杂度分析
时间复杂度：O(N)。此处的n指的是 s 字符串长度。
空间复杂度：O(C)。非重复字符，包含四大类别，以ASCⅡ码值作标的，不超过128；
备注
集合替换哈希表，数据量缩小一半；
双指针遍历，且使用指针计算最大长度，去除长度计算与容器的关联，无需清空容器；
一次遍历无须回退。
关于滑动窗口的补充
已知滑窗大小k的情况下，枚举滑窗右端点，根据滑窗大小可以推理，得到左端点的值
滑窗大小为求解对象时，左右指针如何初始化便于遍历？
左右指针均初始化为0
左指针初始为0,删除操作从index = 1开始，右指针初始化为-1
两种初始化的比较：
后者的优越性体现在哪里？
遍历时无需考虑对两种情况的特判：1. 左指针不动，右指针向右移动（遇到字符连续且非重复）2. 左指针向右移动一位，右指针移动两位（遇到：当前字符与容器中左端点字符重复）；其次尽可能做到不重不漏。
哪一种方式更加符合数学常理呢？
使用滑动窗口元素个数的计算公式sclae = right - left + 1，对于前者，当指向同一个位序时，元素个数为1，对于后者，当左右指针分别指向0，-1时，元素个数 scale = (-1) - 0 + 1 = 0，数学意义上更加严谨
思考滑动窗口的本质是什么？
本质是一个区间，如果两个指针指向同一个位序，视觉上等价于区间为空；
刷题过程
V1
rate: 282/987
wrong case: "pwwkew" expected result: 3 specifical result: 4
重定向的时候，应该清空整个容器，否则对于样例ACCDEF来说，本来应该取CDEF，由于之前仅删除了ACC中的第二个，字典中还存留一个A，导致实际输出结果比预期结果大1
V2
AC版本
V3
rate: 945/987
wrong case aab， expected result: 2, factual result: 1
V4
27 / 987
继续修改：用双指针计算距离，进一步削弱容器的作用
反思：还是按照回退的思路移动指针，却没有修改容器中的元素，二者强关联；
chatGPT优化版本
考虑优化字典的使用。
在这段代码中，每当出现重复元素时，都需要将整个字典清空，相当于把已经扫描过的字符的位置信息全部丢弃。
为了避免这种浪费，我们可以将字典改为记录每个字符上一次出现的位置，而不是第一次出现的位置。这样，当我们找到重复元素时，可以直接将left指针跳到该元素上一次出现的位置的下一个位置，从而避免了清空字典的操作。
在具体实现时，不管字符是否在字段中出现，均将其添加到字典中；
对于已经在字典中出现的字符，将left指针跳到该字符上一次出现的位置的下一个位置，更新该字符在字典中的索引，并且求出当前子串长度并更新maxLen。
这样的优化可以进一步提高代码的效率，时间复杂度为O(n)，空间复杂度为O(min(n,m))，其中m为字符集大小。
修改后的代码如下：
思考中文字整理
不定长字符串，字符串长度即 K 就是我们要求的值
字符串的特征：四种类型，字母，数字，符号和空格
数据结构：set()自带去重
len(set(nums)) = 1, result = 1
目标数据特征：
连续，且元素不重复 如何确保连续？顺序遍历 不重复？集合
如何计算？如果出现连续字符，则清空集合；非重，则继续遍历，更新最大长度为集合长度，
如果在当前元素重复，准备回退时不清空哈希表，那么已经在哈希表的元素会直接影响，显然，回退时，可以不删除重复元素-位序这组键值对吗？不能，如果未删除，将陷入死循环，在一个字符两次出现的位置反复遍历；
当出现第一个同种字符时，清空集合后应该再插入该字符，这个字符可能作为下一个连续不重复字符串的头部，后来将这个思路转化为后退到某个字符第一次出现位置的下一个，那么无需再插入一个元素维持平衡
407/987 由于一次遍历，不能重定向起始位置，而是顺着重复字符继续向下寻找，而可能出现重复字母不连续，两个字母之间存在间隔的情况
此时应该重定位，从重复字母首次出现的位置的下一个位置继续遍历，而不是顺着当前位置【某个字符第二次出现】继续遍历
计算：即使重定位，那么之前按照字典长度来计算最长子字符串，不会影响结果，只有本次遍历到的子字符串更长，才能添加进去，从而改变长度
marked: 以后能否自己构造测试样例，自我折磨呢？
有没有一种结构，既可以判断重复，又可以满足回退，此时回退的是当前字符第一次出现的位置，可是我们如何给它定界呢？
所以用两个指针来处理字符以及字符回退的问题，但是容器能够和双指针搭配吗?回退的时候，如何保证位序和元素的一致性呢？进一步思考：一致性表达的是，当回退的时候，退到那个位置，并且集合中已有的元素如何处理？
能不能直接用指针计算目标字符串的长度，从而摆脱对集合的操作？
现在的循环是一次 while 加判断，可以写成 for 内嵌 while,那么可以保存非重复字串的左右字符，这不就可以验证重复【此举仍然会将复杂度推到 O(N^2)
先定义 left 和 right ？此题与滑动窗口之间的关联？可将最长非重复子串看做是 k，非重复的最后一个子母看做是滑窗的右端点，最长非重复子串的开始位置看做是左端点 如何滑动？仍然通过指针滑动，判断的条件是字符是否重复，即是否已经被包含在哈希表中
标签：
