13
面试刷题-滑动窗口-无重复字符的最长子串
source link: http://www.banbeichadexiaojiubei.com/index.php/2020/12/27/面试刷题-滑动窗口-无重复字符的最长子串/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
题目-无重复字符的最长子串
链接: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
给定一个字符串，找出其中不含有重复字符的 最长子串 的长度。
步骤一。来源:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/hua-jie-suan-fa-3-wu-zhong-fu-zi-fu-de-zui-chang-z/
步骤二。来源:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/hua-jie-suan-fa-3-wu-zhong-fu-zi-fu-de-zui-chang-z/
步骤三。来源:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/hua-jie-suan-fa-3-wu-zhong-fu-zi-fu-de-zui-chang-z/
步骤四。来源:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/hua-jie-suan-fa-3-wu-zhong-fu-zi-fu-de-zui-chang-z/
步骤五。来源:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/hua-jie-suan-fa-3-wu-zhong-fu-zi-fu-de-zui-chang-z/
步骤六。来源:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/hua-jie-suan-fa-3-wu-zhong-fu-zi-fu-de-zui-chang-z/
步骤七。来源:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/hua-jie-suan-fa-3-wu-zhong-fu-zi-fu-de-zui-chang-z/
我们可以使用 「滑动窗口」 来解决这个问题，使用两个指针表示字符串中某个子串的左右边界。在每一步操作中，我们将左指针向右移动一格，表示子串的起始位置，然后不断的向右移动右指针，但要保证这两个指针对应的子串没有重复的字符。如果出现重复的字符，将左指针移动到首个不重复的字符，如此重复，直到得到所有最长不重复字符的子串长度。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
std::unordered_set<char> char_set;
int left = 0;
int ans = 0;
for (int i = 0; i < s.length(); i++) {
while (char_set.count(s.at(i)) > 0) {
char_set.erase(s.at(left));
++left;
}
ans = std::max(ans, i - left + 1);
char_set.insert(s.at(i));
}
return ans;
}
};
除非注明，否则均为[半杯茶的小酒杯]原创文章，转载必须以链接形式标明本文链接
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK