題目：leetcode 3. 無重復(fù)字符的最長子串
給定一個字符串，請你找出其中不含有重復(fù)字符的 最長子串 的長度。
示例 1:
輸入: s = "abcabcbb"
輸出: 3
解釋: 因為無重復(fù)字符的最長子串是 "abc"，所以其長度為 3。
子串：串中任意個連續(xù)的字符組成的子序列稱為該串的子串。
解題思路
要求字符串的不含有重復(fù)字符的最長子串的長度，只需要先找到最長子串然后再求其長度即可，找最長子串我們可以通過滑動窗口的方法去查找。
滑動窗口
滑動窗口就是通過不斷調(diào)整子序列的 start 和 end 位置，從而獲取滿足要求的結(jié)果。
具體操作如下：
1、假設(shè)已經(jīng)找到一個不含重復(fù)字符子串 s[left...right]，s[left...right] 表示從字符串 s 的下標(biāo) left 到 right 的子串。
2、子串?dāng)?shù)組的右邊界 right 向右移，拓展子串長度，以尋找最長子串。
3、將字符 s[right + 1] 跟子串 s[left...right] 中的每個字符進行比較，如果都不同，則將字符 s[right + 1] 也納入到子串中。
4、如果字符 s[right + 1] 跟子串 s[left...right] 中的某個字符相同，則將子串?dāng)?shù)組的左邊界 left 右移，刨除 s[left...right] 中的那個重復(fù)的字符；
刨除前
刨除后
5、left 到 right 這個區(qū)間形成一個滑動窗口，為了尋找滿足條件的子串，窗口不停地在向前滑動，記錄子串的長度是否是更長的子串。
細節(jié)
如何判斷右邊界 right 向右拓展時，其對應(yīng)的字符和當(dāng)前找到的子串中無重復(fù)字符呢？一個簡單的方法是：設(shè)置一個數(shù)組記錄 ASCII 碼出現(xiàn)的頻率，這樣當(dāng) right 向右拓展時，就可以查找其對應(yīng)的字符對應(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};
/* 定義滑動窗口為 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ù)元素，并將此時左邊界對應(yīng)的字符出現(xiàn)的次數(shù)在 freq 的記錄中減一 */
} else {
freq[s[l++]]--;
}
/* 當(dā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;
}
