給定一個字符串，請你找出其中不含有重復(fù)字符的 最長子串 的長度。
示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 因為無重復(fù)字符的最長子串是 "abc"，所以其長度為 3。
示例 2:
輸入: "bbbbb"
輸出: 1
解釋: 因為無重復(fù)字符的最長子串是 "b"，所以其長度為 1。
示例 3:
輸入: "pwwkew"
輸出: 3
解釋: 因為無重復(fù)字符的最長子串是 "wke"，所以其長度為 3。
請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串。
鏈接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
1.滑動窗口法，個人理解就基本上類似棧的原理，只是在將元素剔除出當(dāng)前序列時是有選擇的，在每次有元素進入序列時，尋找是否有與當(dāng)前元素相同的元素在序列中，如有就記錄當(dāng)前長度，然后將開頭到與當(dāng)前元素相同元素的位置所有元素剔除
List： 執(zhí)行用時：96 ms 內(nèi)存消耗：24.9 MB? 時間復(fù)雜度：O(n)? n = s.Length
public int LengthOfLongestSubstring(string s)
{
? ? ? ? int maxLength = 0;
? ? ? ? List<char> ls = new List<char>();
? ? ? ? for (int i = 0; i < s.Length; i++)
? ? ? ? {
? ? ? ? ? ? if (ls.Contains(s[i]))
? ? ? ? ? ? {
? ? ? ? ? ? ? ? ls.RemoveRange(0, ls.IndexOf(s[i]) + 1);
? ? ? ? ? ? }
? ? ? ? ? ? ls.Add(s[i]);
? ? ? ? ? ? maxLength = ls.Count > maxLength ? ls.Count : maxLength ;
? ? ? ? }
? ? ? ? return maxLength ;
? ? }
2. 頭到尾滑一遍，遇到重復(fù)的就去頭部的一位，每次滑動就保存一下長度，最后返回最大長度
Queue：執(zhí)行用時：128 ms 內(nèi)存消耗：25.1 MB
public class Solution {
? ? public int LengthOfLongestSubstring(string s) {
? ? ? ? ? ? ? ? int max = 0;
? ? ? ? ? ? ? ? Queue<char> q = new Queue<char>();
? ? ? ? ? ? ? ? foreach (char c in s)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? while (q.Contains(c))
? ? ? ? ? ? ? ? ? ? ? ? q.Dequeue();
? ? ? ? ? ? ? ? ? ? q.Enqueue(c);
? ? ? ? ? ? ? ? ? ? if (q.Count > max)
? ? ? ? ? ? ? ? ? ? ? ? max = q.Count;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? return max;
? ? }
}
3.子串不停的加長，每加一個字符，就進行子串內(nèi)部的對比，如果發(fā)現(xiàn)有重復(fù)的，則判斷當(dāng)前是否為最大值，并以發(fā)現(xiàn)的位置+1做為新的起點。這里要注意的是有重復(fù)時，end表示已重復(fù)的位置，因此end-start即可，不用再加1
public int LengthOfLongestSubstring(string s)
{
? ?? int start = 0;
? ?? int end = 0;
? ?? int max = 1;
? ?? if (s.Length == 0)
? ? ? ? ? return 0;
? ? for (int i = 0; i < s.Length - 1; i++)
?? {
? ? ? end++;
? ? ?? for (int t = start; t < end; t++)
? ? ? {
? ? ? ? ? ? if (s[t] == s[end] )
? ? ?? {
? ?? if (end - start? > max)
? ? ? ? max = end - start ;
? ? ? ?? start = t + 1;
? ? ? ? ? break;
? ? ? ? }
? ?? }
? ? }
? if (end - start + 1 > max)
? ? ?? max = end - start + 1;
? return max;
}
