初始化 ans for 初始化慢指针 = 0， 快指针 = 0 in 可迭代集合 更新窗口内信息 while 窗口内不符合维护的条件 扩展或者收缩窗口 慢指针移动 if 是合法的答案 更新答案 返回 ans
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是"wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke"是一个子序列，不是子串。
看到这道题我首先想到的是用Python的字典，C++的map来实现，先定义一个first指针指向-1，之后挨个遍历字符串，将遍历到的字符记录为Key值，Value为该字符在字符串中的位置，之后当遍历时只要有重复字符出现时，也就意味着相同的Key值要进入字典，此时将最先记录Key值的字符的Value值赋给first指针，就此时的状态而言，最长无重复子串=该字符在字符串中的位置-first指针所指的值(也就是该字符上一次在字符串中出现的位置)，当每次字符串向后遍历一位时，都记录最长无重复子串的最大值，以此类推对最大值进行更新，求出最长无重复字符子串。
#include <unordered_map>
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char,int> d;//无序map
int first = -1,max = 0,n=s.size();
for(int i=0;i<n;i++)
{
if (d.find(s[i])!=d.end() && d[s[i]]>first)//s[i]在map中存在且在字符串中的位置大于first指针
{
first= d[s[i]];//将原先该字符的value值赋给first指针
d[s[i]] = i;//更新该字符现在的value值
}
else
d[s[i]]= i;
if (i-first >=max)
{
max = i-first;
}
}
return max;
}
};
class Solution(object):
def lengthOfLongestSubstring(self, s):
first = -1
max = 0
d = {}
for i in range(len(s)):
if s[i] in d and d[s[i]]>first:
first = d[s[i]]
d[s[i]] = i
else:
d[s[i]] = i
if i - first >= max:
max = i -first
return max
大概意思是：始终保证左右指针之间的字符串为无重复子串，遍历字符串统计出最长的无重复子串
难想的是左指针向右移动的时机，官方给的题解很巧妙，在每次大循环时，都会将左指针向右移动一格，那么问题的关键就变成了右指针停止的条件，即左指针所指的字符重复出现的时机。在什么情况下能直接判断出字符是否重复出现呢，对，是set容器！我们只要将每个统计过的字符加入了set容器，那么当set容器中存在的值再次出现时，我们便知道此时右指针该停止移动了，该左指针移动！
所以便能写出关键代码：
while (rk + 1 < n && !occ.count(s[r + 1])) {
// 不断地移动右指针
occ.insert(s[r + 1]);
++rk;
}
从而写出完整代码：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_set<char> occ;//建立无序set容器
int n=s.size();
int r=-1;
int ans =0;
for (int i=0;i<n;i++)
{
if (i!=0){//将最左边元素出集合
occ.erase(s[i-1]);
}
while(r+1<n && !occ.count(s[r+1]))//右指针继续遍历条件
{
occ.insert(s[r+1]);//集合中加入右指针所指字符
r++;
}
ans = max(ans,r-i+1);
}
return ans;
}
};
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
occ = set()
n = len(s)
r, ans = -1, 0
for i in range(n):
if i != 0:
occ.remove(s[i - 1])
while r + 1 < n and s[r + 1] not in occ:
occ.add(s[r + 1])
r += 1
# 第 i 到 r 个字符是一个极长的无重复字符子串
ans = max(ans, r - i + 1)
return ans
这道题只要理解了思路，不是很难做，难在思路和一些地方具体代码的实现。双指针在做数组，字符串，链表等问题时使用频率很高，需要熟练掌握。
涉及知识：双指针
C++ ：map容器， set容器
Python： 字典 ，set()函数
相关问题可在我的专栏中查看：