[LeetCode] 无重复字符的最长子串

今天药忘吃喽~ 2022-05-28 09:38 184阅读 0赞

### 无重复字符的最长子串 ###

#### 英文描述 ####

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.

--------------------

#### 中文描述 ####

给定一个字符串，找出不含有重复字符的 最长子串 的长度。

示例：

给定 “abcabcbb” ，没有重复字符的最长子串是 “abc” ，那么长度就是3。  
给定 “bbbbb” ，最长的子串就是 “b” ，长度是1。  
给定 “pwwkew” ，最长子串是 “wke” ，长度是3。请注意答案必须是一个子串，”pwke” 是 子序列 而不是子串。

--------------------

算法参考：`https://www.nowcoder.com/questionTerminal/5947ddcc17cb4f09909efa7342780048`

"滑动窗口解法"
    比方说 abcabccc 当你右边扫描到abca的时候你得把第一个a删掉得到bca，
    然后"窗口"继续向右滑动，每当加到一个新char的时候，左边检查有无重复的char，
    然后如果没有重复的就正常添加，
    有重复的话就左边扔掉一部分（从最左到重复char这段扔掉），在这个过程中记录最大窗口长度

通过代码：

int lengthOfLongestSubstring(string inputString) 
        {
            unordered_map<char, int> charMap = {};
            int maxLength = 0;
            int leftPos = 0;
            for (auto i = 0; i < inputString.size(); i++)
            {
                char curChar = inputString[i];// 当前字符
    
                if (charMap.find(curChar) != charMap.end())
                {
                    // 当前字符已经出现过,找到其位置
                    int existCharPos = charMap[curChar];
                    leftPos = max(leftPos, existCharPos + 1);
                }
                maxLength = max(maxLength, i - leftPos + 1);
                charMap[curChar] = i;
            }
    
            return maxLength;
        }