面试题48：最长不含重复字符的子字符串（C++）
2021-02-02 10:15
标签：ret long 哈希表 sts 判断 one 记录 font return 题目地址：https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/ 请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。 示例 1: 输入: "abcabcbb" 输入: "bbbbb" 输入: "pwwkew" 暴力法：将字符串中的每个字符存储到字符串ss中，然后判断字符串s中的每个字符是否出现在字符串ss中，即是否重复。 哈希表：使用哈希表记录每个字符的下一个索引，然后向右移动右指针right来拓展滑动窗口的大小，并更新窗口的最大长度res。如果右指针right指向的元素s[right]重复，则将左指针left直接移动到窗口中重复元素的右侧。 Set去重：使用set对字符串s去重，如果当前字符未出现在set中，则end右移，并把该字符插入set中，否则遇到重复元素，则从set中删除。 双指针：使用快慢指针，从左往右移动滑动窗口，判断快指针right指向的元素是否出现在滑动窗口内，如果窗口内没有该元素，则将该元素加入滑动窗口，同时更新窗口长度最大值，否则如果窗口存在该元素，即遇到重复元素，移动慢指针left，直到窗口中不包含该元素。 暴力 哈希表 Set去重 双指针 参考文章 https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/solution/c-hua-dong-chuang-kou-shuang-zhi-zhen-ha-xi-biao-j/ https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/solution/lioney-cqiao-yong-biao-ji-wei-by-lioney/ 面试题48：最长不含重复字符的子字符串（C++） 标签：ret long 哈希表 sts 判断 one 记录 font return 原文地址：https://www.cnblogs.com/wzw0625/p/12810918.html题目描述
题目示例
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。解题思路
程序源码
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.size() == 0) return 0;
int res = 0;
for(int i = 0; i )
{
string ss = "";
ss += s[i];
for(int j = i + 1; j )
{
if(find(ss.begin(), ss.end(), s[j]) == ss.end()) ss += s[j];
else break;
}
if(ss.size() > res) res = ss.size();
}
return res;
}
};
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.size() == 0) return 0;
unordered_mapchar, int> mp;
int res = 0;
int left = 0, right = 0;
while (right s.size()) {
if (mp.find(s[right]) != mp.end()) {
left = max(left, mp[s[right]] + 1); //更新窗口起始位置left，例如abba，扫描到最后一个a时，left的原始位置为2
}
mp[s[right]] = right;
right++;
res = max(right - left, res);
}
return res;
}
};
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.size() == 0) return 0;
int res = 0;
int begin = 0, end = 0;
setchar> count_ch;
for(int i = 0; i )
{
while(count_ch.count(s[i]) != 0)
{
count_ch.erase(s[begin++]);
}
count_ch.insert(s[i]);
end++;
res = max(end - begin, res);
}
return res;
}
}；
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.size() == 0) return 0;
int res = 0;
int right = 0;
for(int i = 0; i )
{
int left = right;
while(left i)
{
if(s[left] == s[i]) right = left + 1;
left++;
}
res = max(i - right + 1, res);
}
return res;
}
};
文章标题：面试题48：最长不含重复字符的子字符串（C++）
文章链接：http://soscw.com/index.php/essay/49917.html