題目：leetcode 3. 無重復(fù)字符的最長(zhǎng)子串
給定一個(gè)字符串辨赐，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度宣增。
示例 1:
輸入: s = "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是 "abc"车遂，所以其長(zhǎng)度為 3封断。
子串：串中任意個(gè)連續(xù)的字符組成的子序列稱為該串的子串。
解題思路
要求字符串的不含有重復(fù)字符的最長(zhǎng)子串的長(zhǎng)度舶担，只需要先找到最長(zhǎng)子串然后再求其長(zhǎng)度即可坡疼，找最長(zhǎng)子串我們可以通過滑動(dòng)窗口的方法去查找。
滑動(dòng)窗口
滑動(dòng)窗口就是通過不斷調(diào)整子序列的 start 和 end 位置衣陶，從而獲取滿足要求的結(jié)果柄瑰。
具體操作如下：
1闸氮、假設(shè)已經(jīng)找到一個(gè)不含重復(fù)字符子串 s[left...right]，s[left...right] 表示從字符串 s 的下標(biāo) left 到 right 的子串教沾。
2蒲跨、子串?dāng)?shù)組的右邊界 right 向右移，拓展子串長(zhǎng)度授翻，以尋找最長(zhǎng)子串或悲。
3、將字符 s[right + 1] 跟子串 s[left...right] 中的每個(gè)字符進(jìn)行比較堪唐，如果都不同巡语，則將字符 s[right + 1] 也納入到子串中。
4羔杨、如果字符 s[right + 1] 跟子串 s[left...right] 中的某個(gè)字符相同捌臊，則將子串?dāng)?shù)組的左邊界 left 右移杨蛋，刨除 s[left...right] 中的那個(gè)重復(fù)的字符兜材；
刨除前
刨除后
5、left 到 right 這個(gè)區(qū)間形成一個(gè)滑動(dòng)窗口逞力，為了尋找滿足條件的子串曙寡，窗口不停地在向前滑動(dòng)，記錄子串的長(zhǎng)度是否是更長(zhǎng)的子串寇荧。
細(xì)節(jié)
如何判斷右邊界 right 向右拓展時(shí)举庶，其對(duì)應(yīng)的字符和當(dāng)前找到的子串中無重復(fù)字符呢？一個(gè)簡(jiǎn)單的方法是：設(shè)置一個(gè)數(shù)組記錄 ASCII 碼出現(xiàn)的頻率揩抡，這樣當(dāng) right 向右拓展時(shí)户侥，就可以查找其對(duì)應(yīng)的字符對(duì)應(yīng)的 ASCII 碼在該數(shù)組中相應(yīng)的頻率值的多少判斷是否出現(xiàn)了重復(fù)字符。
Show me the Code
// c 語言
int lengthOfLongestSubstring(char * s){
int res = 0;
int len = strlen(s);
/* 記錄 ASCII 字符在子串中出現(xiàn)的次數(shù) */
int freq[256] = {0};
/* 定義滑動(dòng)窗口為 s[l...r] */
int l = 0, r = -1;
while (l < len) {
/* freq 中不存在該字符峦嗤，右邊界右移蕊唐，并將該字符出現(xiàn)的次數(shù)記錄在 freq 中 */
if (r < len - 1 && freq[s[r + 1]] == 0) {
freq[s[++r]]++;
/* 右邊界無法拓展，左邊界右移烁设，刨除重復(fù)元素替梨，并將此時(shí)左邊界對(duì)應(yīng)的字符出現(xiàn)的次數(shù)在 freq 的記錄中減一 */
} else {
freq[s[l++]]--;
}
/* 當(dāng)前子串的長(zhǎng)度和已找到的最長(zhǎng)子串的長(zhǎng)度取最大值 */
res = fmax(res, r - l + 1);
}
return res;
}
// c++ 語言
int lengthOfLongestSubstring(string s) {
int res = 0;
int len = s.size();
int freq[256] = {0};
int l = 0, r = -1;
while (l < len) {
if (r + 1 < len && freq[s[r + 1]] == 0) {
freq[s[++r]]++;
} else {
freq[s[l++]]--;
}
res = max(res, r - l + 1);
}
return res;
}
