1、题目描述
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例 1:
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。
2、VS2019上运行
滑动窗口的方法文章来源：https://www.toymoban.com/news/detail-659362.html
#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
class Solution {
public:
int lengthOfLongestSubstring(string s) {
// 哈希集合，记录每个字符是否出现过
unordered_set<char> occ;
int n = s.size();
// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
int rk = -1, ans = 0;
// 枚举左指针的位置，初始值隐性地表示为 -1
for (int i = 0; i < n; ++i) {
if (i != 0) {
// 左指针向右移动一格，移除一个字符
occ.erase(s[i - 1]);
}
while (rk + 1 < n && !occ.count(s[rk + 1])) {
// 不断地移动右指针
occ.insert(s[rk + 1]);//将字符 s[rk + 1] 插入到哈希集合 occ 中。这样做的目的是记录窗口中出现过的字符
++rk;
}
// 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = max(ans, rk - i + 1);//比较滑动窗口的大小
}
return ans;
}
};
int main() {
Solution solution;
string s = "abcabcbb";
int length = solution.lengthOfLongestSubstring(s);
cout << "Length of the longest substring without repeating characters: " << length << endl;
return 0;
}
Length of the longest substring without repeating characters: 3文章来源地址https://www.toymoban.com/news/detail-659362.html
3、解题思路
- 1.如果 i 不等于 0，即左指针不在初始位置：
- 2.从哈希集合 occ 中移除左指针所对应的字符（即滑动窗口左边界向右移动一格，移除一个字符）。
- 3.不断移动右指针 rk，直到滑动窗口中出现重复字符或者右指针到达字符串的末尾：
- 4.检查右指针所对应的字符 s[rk+1] 是否在哈希集合 occ 中。
- 5.如果 s[rk+1] 不在集合中，则将 s[rk+1] 插入到集合 occ 中，以记录窗口中出现过的字符。
- 6.右指针 rk 向右移动一格（++rk）。
- 7.计算当前滑动窗口的大小（即右指针减去左指针再加上 1），并与更新 ans 的值进行比较，取较大的值作为新的 ans。
- 8.循环进行下一轮迭代，更新左指针 i，直到遍历完字符串 s 的所有位置。
- 通过不断移动左指针和右指针，循环遍历了所有可能的滑动窗口，找到了最长的无重复字符子串的长度。
4、count()函数
- count() 是一种用于确定容器中特定元素出现次数的函数。在 C++ 中，count() 函数通常用于容器类，如字符串、向量、列表、集合等。在这些容器中，count() 函数用于计算指定元素出现的次数。
- 对于哈希集合 occ，occ.count(s[rk + 1]) 用于计算 s[rk + 1] 在集合 occ 中的出现次数。如果 s[rk + 1] 在集合中存在，则返回 1；如果不存在，则返回 0。
- 哈希集合是一种不允许重复元素的容器。因此，对于哈希集合来说，count() 函数的返回值只能是 0 或 1。
到了这里，关于剑指Offer48.最长不含重复字符的子字符串 C++的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
