題目在問什麼
給一個字串 s，找出最長的不重複子字串長度。
這裡要注意的是：
- 題目要的是
substring - 不是只要挑幾個不重複字元就好
也就是說，字元一定要連續。
例子
Input: s = "abcabcbb"
Output: 3
Explanation: "abc"Input: s = "pwwkew"
Output: 3
Explanation: "wke"解題思路
這題很典型的做法是：
HashSet<char>+ sliding window- 也就是
two pointers
我們維護一個目前視窗內不重複的字元集合，並用兩個指標表示視窗範圍：
startIdx：視窗左邊界endIdx：視窗右邊界
流程如下：
- 如果
s[endIdx]還沒出現在集合裡，就把它放進來 - 接著更新目前最長長度
- 如果
s[endIdx]已經重複，就把左邊界一路右移，直到重複字元被移出視窗
為什麼不能整段重置
很多人一開始會想到：
- 只要遇到重複，就把整個集合清掉重新開始
但這樣會把還能保留的有效區間一起丟掉。
例如：
"dvdf"正確答案是 "vdf"，長度 3。
如果重複就整段重來，通常只會拿到 "df"，長度 2。
所以這題的核心不是重開，而是把左邊界精準往前推。
代碼
public class Solution
{
public int LengthOfLongestSubstring(string s)
{
HashSet<char> charHash = new HashSet<char>();
int maxLength = 0;
int startIdx = 0;
int endIdx = 0;
while (endIdx < s.Length)
{
if (!charHash.Contains(s[endIdx]))
{
charHash.Add(s[endIdx]);
endIdx++;
maxLength = Math.Max(maxLength, endIdx - startIdx);
}
else
{
charHash.Remove(s[startIdx]);
startIdx++;
}
}
return maxLength;
}
}複雜度
- 時間複雜度：
O(n) - 空間複雜度：
O(min(n, charset))
這題先記住的重點
- 看到「最長不重複連續區間」先想 sliding window
- 視窗內重複時，不要整段重置，只要縮左邊界
substring和subsequence要分清楚