Leetcode--003--重複文字のない最長文字列【C++、スライドウィンドウ】

萌新记录~よろしくお愿いします:)来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
タイトルには文字列が指定されています.重複文字が含まれていない長男列の長さを見つけてください.
例1:入力:「abcabcbb」出力:3説明:重複文字のない長男列が「abc」であるため、その長さは3である.
例2:入力:「bbbb」出力:1説明:重複文字のない最長子列は「b」であるため、その長さは1である.
例3:入力:「pwwkew」出力:3説明:重複文字のない最長子列は「wke」であるため、その長さは3である.
あなたの答えはサブストリングの長さでなければなりません.「pwke」はサブストリングであり、サブストリングではありません.
考え方:ウィンドウをスライドしようとする最初の問題文字列s

STEP 1は空の配列mを定義し[256]、左境界left=0、右境界はiループsを通過する.ここではASCIIが256文字を表すことができるため,出現したすべての文字を記録することができる.

STEP 2文字列sをループすることにより、m[s[i]]が0であるか否かを判断し、0である場合は以前に現れなかったことを示し、leftは変わらずres値を更新し、m[s[i]]値を更新する.ここで、sの下付き文字は0から始まるので、長さresを計算する場合は、i-leftを用いた後も+1すべきである.例えばabcd left=0、i=3の場合は重複文字がない、res=i-left+1=3-0+1=4である.

STEP 3 m[s[i]!=0は、現在のスライドウィンドウに同じ要素が含まれていることを示し、左境界left=m[s[i]]を縮小する.m[s[i];このm[s[i]]配列は,最近s[i]が出現した位置の次の下付き文字を格納する.(我々は本質的に重複要素が現れると、スライドウィンドウで前回現れた要素を削除し、leftを次の位置に置くため)

STEP 4はまた、abbcaがi=4のとき配列m[a]=1 m[b]=3 m[c]=4のときのleft=2 m[s[4]=m[a]=1のときは0ではないがスライドウィンドウに追加すべきであるため、判断時にはm[s[i]]も判断すべきであることに注意すべきである

実は条件は2つあります:1つ目はm[s[i]==0説明は現れたことがなくて、きっとウィンドウ

に追加することができます

の2番目はm[s[i]!=0の場合、前のleftが増加したのは、その後重複する要素があったためかもしれないので、条件を満たさないとは直接言えません.

リファレンスコード

#include 
#include 
#include 

using namespace std;

int LengthofLongeststring(string s)
{
    int m[256];
    memset(m,0,sizeof(m));

    int res=0,left=0;
    for(int i=0;i<s.size();i++)
    {
        if(m[s[i]]==0 || m[s[i]]<left)
        {
            res=max(res,i-left+1);
        }
        else
            left=m[s[i]];
        m[s[i]]=i+1;
    }
    return res;
}
int main()
{
    string s;
    getline(cin,s);

    int ans;
    ans=LengthofLongeststring(s);
    cout << ans <<endl;
    return 0;
}