問題#
【無重複字符的最長子串】給定一個字符串 s
,請你找出其中不含有重複字符的 最長子串 的長度。
解法一:滑動窗口 + 哈希表#
求最大長度#
Console.WriteLine(LengthOfLongestSubstring("abcabcbb"));
Console.WriteLine(LengthOfLongestSubstring("bbbbb"));
Console.WriteLine(LengthOfLongestSubstring("pwwkew"));
// 得到給定字符串中最大不重複的子字符串的長度
int LengthOfLongestSubstring(string str)
{
if (string.IsNullOrWhiteSpace(str)) return 0;
// 哈希表統計字符 str[right] 最後一次出現的索引
Dictionary<char, int> dic = new();
// 定義左指針(-1和0都可以),最大不重複子字符串的長度
int left = -1, res = 0;
// 不斷地增加 right 擴大窗口
for (int right = 0; right < str.Length; right++)
{
//Console.WriteLine($"向右擴大區間: [{left}, {right}]");
var currentChar = str[right];
if (dic.ContainsKey(currentChar))
{
// 不斷增加 left 縮小窗口,因為遇到了重複的字符,更新左指針為重複值的索引
left = dic[currentChar];
//Console.WriteLine($"向右縮小區間: [{left}, {right}]");
}
// 更新哈希表記錄:當前遍歷的字符最後一次在字符串中的出現的索引
dic[currentChar] = right;
// 更新結果:用右指針減去左指針,得到雙閉區間內最大不重複子串的長度
// 再用 Max 函數取上輪 res 和本輪雙指針區間 [left+1, right] 的寬度(即 right -left)中的最大值
res = Math.Max(res, right - left);
//Console.WriteLine($"------第 {right} 輪結果: {res}------{Environment.NewLine}");
}
return res;
}
求最大連續子串#
Console.WriteLine($"結果: {MaxChild("abca2f")}");
Console.WriteLine($"結果: {MaxChild("aabbcc")}");
Console.WriteLine($"結果: {MaxChild("aaaaa")}");
// 最長不重複子串(連續)
string MaxChild(string str)
{
if (string.IsNullOrWhiteSpace(str)) return string.Empty;
Dictionary<char, int> dic = new();
int left = 0;
string res = "";
// [left, right]
for (int right = 0; right < str.Length; right++)
{
// 當前遍歷的字符
char currentChar = str[right];
// 是否已出現過,如果已出現就將左邊界縮小為重複出現的索引
if (dic.ContainsKey(currentChar))
{
// 當包含時代表出現重複字符串,縮小窗口
left = dic[currentChar] + 1;
//Console.WriteLine($"update {currentChar} {right}");
// 更新索引
//dic[currentChar] = right;
dic.Clear();
}
dic[currentChar] = right;
// 更新結果
string sub = str.Substring(left, right - left + 1);
if (sub.Length > res.Length)
{
res = sub;
}
}
return res;
}
(待學習)解法二:動態規劃 + 哈希表#
(看 K 神圖解)