【剣指offer】最長重複文字を含まないサブ文字列(ダブルポインタ)
735 ワード
1、テーマの説明
文字列の中から最も長い重複文字を含まないサブ文字列を見つけて、その長男文字列の長さを計算してください.
文字列には、「a」から「z」までの文字しか含まれていないと仮定します.
サンプル:
入力:abcabc出力:3
2、問題の説明:
3、問題のポイント:ダブルポインタのやり方、1つの前j、1つの後i、最も長い区間(j-i+1)を求めます. は検索が容易で、hashテーブルを使用することができ、重複が発生した場合、iを移動して重複が発生しないまで移動することができます.
4、C++コード:
文字列の中から最も長い重複文字を含まないサブ文字列を見つけて、その長男文字列の長さを計算してください.
文字列には、「a」から「z」までの文字しか含まれていないと仮定します.
サンプル:
入力:abcabc出力:3
2、問題の説明:
3、問題のポイント:
4、C++コード:
class Solution {
public:
int longestSubstringWithoutDuplication(string s) {
unordered_map m;//hash 。
int res;
for (int i = 0, j = 0; j < s.size(); j ++) {
while(m[s[j]]) m[s[i ++]] --;// , i 。
m[s[j]] = 1;// , hash ,
res = max(res, j - i + 1);// 。
}
return res;
}
};