leetcode链接：最长不含重复的子字符串
题目描述
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。
示例 4:
输入: s = ""
输出: 0
提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
方法一
这道题可以用动态规划来解，思路解析：https://zhuanlan.zhihu.com/p/80538556
AC代码：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.empty()) return 0;
int cur_len = 0;
int max_len = 0;
int tmp = -1;
std::map<char, int> lastindex;
for(auto i = 0; i < s.length(); i++)
{
if(lastindex.find(s[i]) == lastindex.end()) // not found
{
cur_len++;
}
else
{
tmp = i - lastindex[s[i]];
if(tmp > cur_len)
{
cur_len++;
}
else
{
cur_len = tmp;
}
}
max_len = max(max_len, cur_len);
lastindex[s[i]] = i;
}
return max_len;
}
};
方法二
思路解析：利用 hashset 来检查重复元素。
-
我们定义 l 和 r 两个指针表示一个特定的子字符串的首和尾。初始它们都在索引 0 处。
-
移动 r，并同时向 hashset 中添加 r 所指的元素值，当 r 指到重复的元素时，r - l 的值就是一个不含重复字符的子字符串的长度。
-
erase 掉 haseset 中的 l 所指元素的值，然后让 l++（for 循环的作用）。之后继续移动 r来找到下一个不含重复字符的子字符串的长度。
AC代码：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.size()==0) return 0;
unordered_set<char> store;
int res=-1;
int l=0,r=0;
for(l=0;l<s.size();l++)
{
while(r<s.size()&&!store.count(s[r]))//set的count值只能是0或1
{
store.insert(s[r]);
r++;
}
res=max(res,r-l);
store.erase(s[l]);
if(r>=s.size()) break;
}
return res;
}
};
但因为涉及到频繁的元素erase，这个耗时会比第一种方法略高。
方法三
思路解析：使用滑动窗口来做。
窗口的范围为 [left, right]，left，right初始化为0。
设置一个查找表 lookup，lookup 存储了当前窗口中的元素。right 先移动，如果 s[right] 不在 lookup 中，则 right++，maxLen++，将 right 加入 lookup 中；否则，将 s[left] 从 lookup 中移除（注意这里不是先移除重复的元素 s[right]，因为先移除 s[right] 的话就不满足连续子串这个要求了），将 left++，直至 s[right] 不在 lookup 中出现。当遇到了重复字符，我们一步一步地移动 left 指针。为了加快速度，我们可以直接将 left 移动到当前 right 的位置上。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.empty()) return 0;
vector<int> v(128, -1);
int left = -1;
int maxLen = 1;
for(int right=0; right<s.size(); right++){
char c = s[right];
if(v[c]!=-1) left = max(left, v[c]); // c 出现在了窗口中
v[c] = right;
maxLen = max(maxLen, right-left);
}
return maxLen;
}
};
方法四
双指针，可以直接看代码和注释：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if (!s.size()) return 0; // 判空
int maxLength = 0; // 记录最长不包含重复字符的子字符串的长度
int left = 0, right = 0; // 初始化双指针
unordered_set<char> subStr; // 哈希表存储不包含重复字符的子串
/*
* 双指针遍历原字符串:
* 外层左指针、内层右指针
*/
while (left < s.size()) {
/*
* 右指针不断右移遍历字符串
* 当遇到的字符在哈希表中不存在时，将其插入哈希表
* 遇到哈希表中存在的字符 或 到原字符串结尾时跳出循环
*/
while (right < s.size() && !subStr.count(s[right])) {
subStr.insert(s[right]);
right++;
}
/*
* 更新最大子串的长度
* 因为上面的循环跳出时right指向的是子串后面一个位置
* 所以是right-left而不是right-left+1
*/
maxLength = max(maxLength, right - left);
/*
* 若上面循环跳出是因为右指针到原字符串末尾，
* 说明遍历完毕，最长不包含重复字符的子串已经找到
* 直接跳出循环
*/
if (right == s.size()) break;
/*
* 若上面循环跳出是因为遇到了哈希表中已有的字符
* 则从左边开始挨个删除哈希表中的字符
* 并且左指针右移
*/
subStr.erase(s[left]);
left++;
}
return maxLength;
}
};
方法五
背包
class Solution {
public:
int lengthOfLongestSubstring(string s) {
vector<int> vec(128);
int res = 0, beg = 0, len = s.size();
for(int i = 1; i <= len; ++i) {
auto &x = vec[s[i-1]];
if(beg < x) { beg = x; }
if(res < i - beg) { res = i - beg; }
x = i;
}
return res;
}
};
