AlgoPressAppearance
题目描述
https://leetcode.cn/problems/longest-substring-without-repeating-characters
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：
- 0 <= s.length <= 5 * 10^4
- s 由英文字母、数字、符号和空格组成
思路 : 哈希表/滑动窗口
题目要求找出重复字符的最长子串。 暴力法就是从第一个字符开始，然后遍历到相同字符截止，但是字符创长度是 5*10^4 所以不能用暴力法
我们可以使用哈希表记录位置 假设从开始循环，记录字符到哈希表，遇到相同字符就记录长度，然后从新的地方开始重新记录是否可以？ 如测试数据， dvdf , index=2 的时候发现重复，但是如果从d开始循环，那么长度最后长度是 2 ，就不符合题意了。 所以要从相同字符的下一个字符 v 开始，这样循环到最后是 3 位。
csharp
public class Solution {
public int LengthOfLongestSubstring(string s) {
//思路 Hash 表储存位置，一旦重复，就清空重来
Dictionary<char,int> dict = new Dictionary<char,int>();
int left = 0;
int max = 0;
for(int i=0; i<s.Length; i++){
if(!dict.ContainsKey(s[i])){ //不重复
dict.Add(s[i],i);
}
else{ //重复
//dict.Clear(); //此处不能删除前面所有字符，而是要删掉出现这个字符的位置 : 如测试用例 dvdf
left = Math.Max(dict[s[i]]+1,left); //取到重复位置的下一个
Console.WriteLine("left={0}",left);
dict[s[i]] = i;
}
max = Math.Max(max,i-left+1);
}
return max;
}
}