分析
这道题主要考验滑动窗口的使用。 为了记录字符是否出现过,我们可以使用哈希表来存储每个字符。 用左右指针标明滑动窗口界限。 其中右指针初始值为 -1,左指针初始值为 0。 从而表示此时的滑动窗口为空。
随后我们开始调整滑动窗口。 首先我们可以固定左指针, 当左指针不为0时,左指针会在滑动前滑出指向的字符,从而允许该字符能在右边再次出现。 随后我们开始调整右指针。 右指针会尽可能的向右移动,直到遇到重复的字符或者到达字符串的末尾。 在这期间,程序会更新滑动窗口的最大长度。 从而得出答案。
解答
class Solution {public: int lengthOfLongestSubstring(string s) { unordered_set<char> persist; auto right = -1, ans = 0; int n = s.size();
for (auto left = 0; left < n; ++left) { if (left != 0) persist.erase(s[left - 1]);
while (right + 1 < n && !persist.count(s[right + 1])) persist.insert(s[++right]);
ans = max(ans, right - left + 1); }
return ans; }};