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。