LeetCode第3題重複文字のない最長男列(シロ詳細)

重複しない最長文字列

一、題名説明

例1:

例2:

例3:

二、個人の考え方と解答

で使用するデータ構造:バケツ

C++コード

三、公式問題解

一、テーマの説明
重複文字なしの長男列の難易度:中程度
文字列を指定すると、重複文字が含まれていない長男の列の長さを見つけてください.
例1:
入力:“abcabcbb”出力:3解釈:重複文字のない最長男列は“abc”であるため、その長さは3である.
例2:
入力:「bbbbb」出力:1解釈:重複文字のない長男列は「b」であるため、その長さは1である.
例3:
入力:「pwwkew」出力:3解釈:重複文字のない長男列は「wke」であるため、その長さは3である.
あなたの答えはサブストリングの長さでなければなりません.「pwke」はサブストリングであり、サブストリングではありません.
通過回数561007  提出回数1601892
二、個人の考え方と解答
この問題は、一見、スライドウィンドウ+バケツで解決すべきだと感じます.  初歩的な考え方は,ウィンドウ右側rightで終わる最長の重複しない文字列を求めることである.rightを1から文字列の末尾に順次スライドさせると、(s[0]以外)文字列の任意の下付き文字列で終わる最長の重複しない文字列がすべて遍歴され、最大値が自然に出てくる.では、「right-1を末尾とする最長重複なし列」の左端点が知られている上で、「rightを末尾とする最長重複なし文字列」を求めるにはどうすればいいのでしょうか.答えは、「right-1で終わる最長重複なし列」では、必ず重複文字はなく、s[right]を加えると、「right-1で終わる最長重複なし列」のいずれかの文字と重複する可能性があります.重複がない場合、今回の長さはright-left+1、重複がある場合は、leftをright-(重複文字の下付き+1)+1に調整する必要があります.
使用するデータ構造:バケツ
まず、文字列である以上、各文字は必ず0〜255の任意の文字であるため、256個のバケツを構築することができる.(時間の複雑さで前回優の方法はhashMap、再び暴力)最後に,maxLengthを記録するための局所変数である.
C++コード

int lengthOfLongestSubstring(string s) {
    if (s.length() == 0) {
        return 0;
    }
    
    int bucket[256];
    for (int i = 0; i < 256; i++) {
        bucket[i] = -1;
    }
    
    // left               ，right                     
    int left = 0, right = 0;
    int maxLength = 0;
    
    while(right != s.length()) {
        if(bucket[s[right]] < left) {
        	//     left  ，            ，       
            if(right-left+1 > maxLength)
                maxLength = right-left+1;
        } else {   //     left    ，         
            left = bucket[s[right]]+1;
        }
        bucket[s[right]] = right;  //       
        right++;  //            
    }
    return maxLength;
}

三、公式問題解
  公式は3つの解法を与えた:多重サイクル、HashMap最適化、バケツ最適化.個人の考え方とほぼ一致しており、余計なことは言わないが、詳細は公式の問題解を参照してください.