leetcode 3. 无重复字符的最长子串

2023.9.15

        本题我用的暴力双层for循环 + unordered_set 解决的，外循环控制字符起始位置，内循环将字符放入 unordered_set，并查找有无重复的元素。  用了一个全局变量记录最长字串的长度，局部变量count记录当前层循环的最长子串长度。 代码如下：

class Solution {
public:int lengthOfLongestSubstring(string s) {if(s.size() == 0) return 0;int ans = 1;for(int i=0; i<s.size(); i++){unordered_set<char> set;set.insert(s[i]);int count = 1;for(int j=i+1; j<s.size(); j++){if(set.find(s[j]) == set.end()) //没找到重复元素{count++;set.insert(s[j]);ans = max(ans , count);}else break;}}return ans;}
};

        暴力循环+每层循环都用了unordered_set，可想而知，时间和空间消耗都相当高... 

        看了下别人的解法，这题还可以用滑动窗口来做。定义一个left指针指向滑动窗口的最左端，for循环的i向前遍历。每当发现重复元素，就不断将set头部元素删除，直到没有重复元素位置。最后不断更新最长子串的长度即可。

        代码如下：

class Solution {
public:int lengthOfLongestSubstring(string s) {if(s.size() == 0) return 0;queue<char> que;int ans = 1;int left = 0;for(int i=0; i<s.size(); i++){while(set.find(s[i]) != set.end()) //找到重复元素了{set.erase(s[left]);left++;}set.insert(s[i]);ans = max(ans , i-left+1);}return ans;}
};