更多精彩文章請關注公眾號：TanLiuYi00
題目
解題思路
題目要求找出給定字串中不含有重復字符的最長子串的長度，這是一個典型的滑動視窗的題目，可以通過滑動視窗去解答，
滑動視窗
具體操作如下圖示：
找到一個子串 s[left...right] 不含重復字符；
為了尋找最長子串，右邊界 right 右移，拓展子串長度；
若此時的字符 s[right + 1] 跟子串 s[left...right] 相比較，s[right + 1] 跟子串中的每個字符都不同，則將字符 s[right + 1] 也納入到子串中；
若此時的字符 s[right + 1] 跟子串 s[left...right] 中的某個字符相同，則將左邊界 left 右移，刨除 s[left...right] 中的那個重復的字符；
刨除后，繼續組成沒有重復元素的子串
...
從 left 到 right 這個區間形成一個滑動視窗，視窗不停向前滑動，尋找不含重復字符的最長子串，記錄子串的長度，并求最長的子串長度，
Show me the Code
int lengthOfLongestSubstring(char * s){
int res = 0;
int len = strlen(s);
/* 存盤 ASCII 字符在子串中出現的次數 */
int freq[256] = {0};
/* 定義滑動視窗為 s[l...r] */
int l = 0, r = -1;
while (l < len) {
/* freq 中不存在該字符，右邊界右移，并將該字符出現的次數記錄在 freq 中 */
if (r < len - 1 && freq[s[r + 1]] == 0) {
freq[s[++r]]++;
/* 右邊界無法拓展，左邊界右移，刨除重復元素，并將此時左邊界對應的字符出現的次數在 freq 的記錄中減一 */
} else {
freq[s[l++]]--;
}
/* 當前子串的長度和已找到的最長子串的長度取最大值 */
res = fmax(res, r - l + 1);
}
return res;
}
更多精彩文章可關注公眾號：TanLiuYi00
歡迎提出意見或建議，如有錯誤，請指出，謝謝！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/259371.html
標籤：其他
上一篇：位元組筆試題 leetcode 69. x 的平方根
下一篇：git02-暫存區和作業區