4.24LongestSubstringWithoutRepeatingCharacters - WisperDin/blog GitHub Wiki

计算字符串中最长无重复字符子串的长度

描述

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.

思路

暴力遍历O(n^3)

扫描全部子串，边扫描边判定子串是否有重复字符

滑动窗口O(n)-O(2n)

扫描字符串，定义

  • 一个本次扫描的子串的起始位置指针 i

  • 一个当前扫描位置的指针 j

  • 存放子串字符元素的 hashset 用于检查重复

开始扫描，对每一个扫描的字符，

  1. 如果没有在hashset有存在，插入这个字符到hashset,当前扫描位置指针往后偏移，计算当前子串长度，若比最大长度要大，更新最大长度；
  2. 如果已经存在，本子串无效，删除hashset中本子串的起始元素，新子串起始位置为原来+1

例子

给定字符串：pwwkewjqc

012345678
pwwkewjqc
hashset（执行后） 当前检查的元素(j指针指向) 是否发现重复
i=0,j=0 p p F
i=0,j=1 p,w w F
i=0,j=2 w w T
i=1,j=2 w T
i=2,j=2 w w F
i=2,j=3 w,k k F
i=2,j=4 w,k,e e F
i=2,j=5 k,e w T
i=3,j=5 k,e,w w F
...

总结：

优点：在于发现当前正在扫描的子串出现即将出现重复字符时，将当前扫描的子串头部往后偏移，而当前扫描位置不变,等待子串头部往后偏移直至没有重复元素之后就可以继续往后扫描

缺点：每次发现重复元素都要从子串头部开始慢慢往后偏移，如果可以知道重复元素的位置，可以加快偏移速度（优化后的滑动窗口）

优化后的滑动窗口O(n)

扫描字符串，定义

  • 一个本次扫描的子串的起始位置指针 i

  • 一个当前扫描位置的指针 j

  • 存放子串字符元素的 hashmap 用于检查重复 (存放扫描到的每个字符以及这些字符的位置，当检查到重复的时候就可以知道当前扫描的字符和哪个位置的字符重复)

在每次扫描中，

  1. 当发现重复时，获取与检查字符重复的字符位置，如果这个位置后一个位置要比当前的i要后，则用这个值更新i（因为在不删除hashmap的情况下，不属于本此扫描子串的元素也会在hashmap中，但是其位置要小于i，所以要加上这条规则防止i回溯的情况发生），
  2. 计算当前长度是否可更新最大长度，将扫描到的字符以及字符位置插入hashmap，continue
hashmap（执行后） 当前检查的元素(j指针指向) 是否发现重复
i=0,j=0 p->0 p F
i=0,j=1 p->0,w->1 w(第一个w) F
i=0,j=2 p->0,w->1 w(第二个w) T
i=2,j=2 p->0,w->2 w(第二个w) F
i=2,j=3 p->0,w->2,k->3 k F
i=2,j=4 p->0,w->2,k->3,e->4 e F
i=2,j=5 p->0,w->2,k->3,e->4 w T
i=3,j=5 p->0,w->5,k->3,e->4,j->6 j F
...
...

滑动窗口实现

class Solution {
public:
    //借助hashset 实现滑动窗口
    int lengthOfLongestSubstring(string s) {
        unordered_set<int> hashset;
        int n = s.size();
        int ans = 0,i=0,j=0;
        //i -- 本次扫描的子串起始位置
        //j -- 扫描位指针
        //ans 结果--子串长度
        while(i<n && j<n){
            //开始扫描字符，若没有存在过，插入hashset，扫描位指针后移，比较 当前子串长度：j-i 是否最大子串长度
            if(hashset.count(s[j])<=0){
                hashset.insert(s[j]);
                j++;
                ans = ans>=j-i?ans:j-i;
            }else{
                //在扫描位发现已经存在的字符，本子串无效，删除hashset中的旧子串起始元素，子串起始位置后移
                hashset.erase(s[i]);
                i++;
            }
        }
        return ans;
    }

};

优化的滑动窗口实现

//优化后的滑动窗口 O(n)
class Solution3 {

public:
    //用hashmap 保存 字符-这个字符的位置  这个value用于发现这个字符重复时在这个字符位置+1后重新开始扫描
    int lengthOfLongestSubstring(string s){
        int n = s.size(),ans = 0;
        unordered_map<int,int> hashmap;
        //i--扫描子串开始位置 
        //j--当前扫描位置
        for(int j=0,i=0;j<n;j++){
            //发现重复
            if(hashmap.count(s[j])>0){
                //对i偏移,只允许i前进
                int nextI = hashmap[s[j]]+1;
                i = i>nextI?i:nextI;
            }
            ans = ans>=j-i+1?ans:j-i+1;
            hashmap[s[j]]=j;
        }        
        return ans;
    }
};
⚠️ **GitHub.com Fallback** ⚠️