(LeetCode刷题)3. 无重复字符的最长子串
题目：
解法一：
class Solution(object): def lengthOfLongestSubstring(self,s): # 哈希集合，记录每个字符是否出现过 occ = set() n = len(s) # 右指针，初始值为-1，相当于我们在字符串的左边界的左侧，还没有开始移动 rk = -1 ans = 0 # 枚举左指针的位置，初始值随便设置 for i in range(n): if i != 0: # 左指针向右移动一格，移除一个字符 occ.remove(s[i - 1]) while rk + 1 < n and s[rk + 1] not in occ: # 不断地移动右指针 occ.add(s[rk + 1]) rk += 1 # 第 i 到 rk 个字符是一个极长的无重复字符子串 ans = max(ans, rk - i + 1) return ans
解法二：
#include <string.h>
#define MAX(a,b) ((a)>(b)?(a):(b))
int lengthOfLongestSubstring(char* s) {
int lastIndex[128]; // 保存字符最后出现的位置
memset(lastIndex, -1, sizeof(int) * 128);
int maxLength = 0; // 存储最大无重复子串的长度
int startPosition = -1; // 滑动窗口起始位置
for(int i=0; s[i]; ++i) {
startPosition = MAX(startPosition, lastIndex[s[i]]);
maxLength = MAX(maxLength, i - startPosition);
lastIndex[s[i]] = i;
}
return maxLength;
}让我们仔细解析一下这段代码：
int lastIndex[128];：定义了一个长度为 128 的数组，用于存储每个 ASCII 字符在字符串中最后出现的位置。数组全部初始化为 -1，表示字符串的初始滑动窗口不含有任何字符。startIndex：用于标记滑动窗口的起始位置。初始化为 -1 表示还没有开始滑动。int maxLength = 0;：用于记录最长无重复字符子串的长度。- 在
for循环中： startPosition = MAX(startPosition, lastIndex[s[i]]);，这个语句在调整窗口的起始位置。如果当前字符s[i]在之前已经出现过（即lastIndex[s[i]]的值大于startPosition），窗口起始位置就需要向前移动一位，以保证窗口内没有重复字符。maxLength = MAX(maxLength, i - startPosition);，这个语句在更新最长无重复字符子串的长度。如果i - startPosition（当前子串长度）更大就进行更新。lastIndex[s[i]] = i;，这个语句在更新当前字符s[i]在字符串 s 中最后出现的位置。
这段代码的主要思想就是，通过控制滑动窗口的起始位置
startPosition 和截止位置 i ，保证窗口内没有重复字符，并在此过程中不断更新最长无重复字符子串的长度 maxLength 。通过这种方式，我们可以在一次遍历中解决问题。
