目录
题目
题解
题目
3. 无重复字符的最长子串 - 力扣（LeetCode）
题解
暴力解法是用两层循环列举出所有可能，并用O(N)的空间复杂度存储临时的字符来判断某个区间是否重复了。
空间复杂度上我们可以用一个哈希表，把空间复杂度降为O(1)。哈希表中存储某个区间字符和字符出现的次数的映射，但我们不必真的定义一个std::unordered_map<char, int>。我们可以int hash[128]代替。
时间复杂度上，我们只需维护一个窗口。算法如下
1.入窗口，把字符映射到hash[128]。
2.判断:
如果这个字符出现的频次超过 1 ，说明窗⼝内有重复元素，那么就从左侧开始划出窗⼝，
直到 ch 这个元素的频次变为 1 ，然后再更新结果。
如果没有超过 1 ，说明当前窗⼝没有重复元素，可以直接更新结果
代码如下：
class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128] = {0}; int left = 0;int right = 0;int s_len = s.size();int ret = 0;while (right < s_len) {hash[s[right]]++; //入窗口while (hash[s[right]] > 1) hash[s[left++]]--;ret = max(ret, right - left + 1);right++;}return ret;}
};
