题目
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
解题
方法一：滑动窗口（逐个）
class Solution {
public:
int lengthOfLongestSubstring(string s) {
//char[] chars = new char[256];
int chars[256]={0}; //ASCII表有127个字符 还有个128的副表 因此申请256个空间 用于计数
int begin = 0;
int res = 0;
for(int i = 0;i<s.length();i++){
while(begin <= i && chars[s.at(i)] > 0){//处理当前添加的字符重复的问题
//下面代码是用于逐个往前滑动 去重
chars[s.at(begin)]--;
begin++;
}
chars[s.at(i)]++;//每次不重复子串的长度+1
res = max(res,i - begin + 1);//记录不重复子串的最长长度
}
return res;
}
};
注意
取单个字符操作：
- C++为 string.at()
- JAVA为 string.charAt()
-
string也可以视为数组形式 直接取就可以 例如 s="abcd",s[2] = "c"。
字符集
方法二
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> data;
int begin = 0, result = 0;
//i代表字串的起始位置，j表示字串的结束位置
for (int j = 0; j < s.size(); j++) {
if (data.find(s[j]) != data.end()) {
begin = max(begin, data[s[j]]);//当有字符重复时更新字串起始位置
}
result = max(result, j - begin + 1);//判断当前字串与历史字串长度的大小
data[s[j]] = j + 1;//记录并更新这个字符最近出现的位置 此处相当于存储之前与之重复的元素的下一个位置
}
return result;
}
};
for (int j = 0; j < s.size(); j++) {
if (data.find(s[j]) != data.end()) {
begin = max(begin, data[s[j]]);//当有字符重复时更新字串起始位置
}
result = max(result, j - begin + 1);//判断当前字串与历史字串长度的大小
data[s[j]] = j + 1;//记录并更新这个字符最近出现的位置
}
不能写为以下这种形式
for (int j = 0; j < s.size(); j++) {
if (data.find(s[j]) != data.end()) {
begin = max(begin, data[s[j]]);//当有字符重复时更新字串起始位置
begin++;
}
result = max(result, j - begin + 1);//判断当前字串与历史字串长度的大小
data[s[j]] = j ;//记录并更新这个字符最近出现的位置
}
错误
这种形式的错误在于，循环有时候会误加，我们本意是取重复元素的下一个作为开始，但是map存储了所有的元素，因此有时即使无效的重复也会进入循环，使begin+1，减少了长度。
上面例子就是，begin在第二个m处时，当运行到最后一个t，由于之前map有保存key为t，因此会进入循环，使begin++，因此长度变短，因此此时的操作属于误操作。
所以直接用数据存储下一个位置这种形式比较可靠。
