Leetcode——3. Longest Substring Without Repeating Characters-蒲公英云

Leetcode——3. Longest Substring Without Repeating Characters

桃扇骨 2022-06-15 10:36 262阅读 0赞

1. 概述

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

这道题需要求取的是在一个字符串中，最长的非重复子串。想到的便是记录扫描过的元素添加到集合中，若是判断新加如的字符与之前的重复了，那么就删除字符，直到不重复为止，在这个过程中记录最大的长度。

这里使用到的方法是滑动窗口算法(Slide Window Algorithm)求解，和 Minimum Size Subarray Sum 相似。
设下标 l 和 r, 把左开右闭 [l, r) 想象成一个窗口。
当 s[r] 和窗口内字符重复时，则 l 向右滑动，缩小窗口。
当s[r] 和窗口内字符不重复时，则 r 向右滑动，扩大窗口，此时窗口内的字符串一个无重复子字符串。
在所有的无重复子字符串中，找到长度最大的，即为原问题解。

2. 编码

class Solution {
public:
    int lengthOfLongestSubstring(string s)
    {
        if("" == s) return 0;   //空串
        if(1 == s.length()) return 1;   //只有一个字符
        if(2==s.length() && s.at(0)!=s.at(1)) return 2;
        int left(0), right(1), len(s.length()), max_len(1);
        unordered_set<int> setv;
        setv.insert(s.at(left));
        while(right < len)
        {
            if(setv.count(s.at(right)) != 0)
            {
                setv.erase(s.at(left));
                ++left;
            }   //在集合中删除元素，直到没有与当前字符重复的时候
            else
            {
                setv.insert(s.at(right));
                ++right;
                max_len = max(max_len, (int)setv.size());   //记录最大的长度
            }
        }
        return max_len;
    }
};