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; isize(); i++)
        {
            unordered_set<char> set;
            set.insert(s[i]);
            int count = 1;
            for(int j=i+1; jsize(); 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; isize(); 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;
    }
};