1、题目描述
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例 1:
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。
2、VS2019上运行
滑动窗口的方法
#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;// 枚举左指针的位置，初始值隐性地表示为 -1for (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
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。
