Day 2 | 3. 无重复字符的最长子串：尝试绕过窗口的一天

错误尝试一用 char 变量维护区间边界我最开始想用类似快慢指针的思路但把指针设成了char类型用left和right记录当前子串的“字符边界”并试图通过right ! s[i]来判断是否重复。public class Solution {public int LengthOfLongestSubstring(string s) {if(s null) return 0;char left s[0];char right left;int num 1;int max 0;for(int i 0; i s.Length - 1; i){if(right ! s[i]){num 1;right s[i];}else{if(max num) max num;num 1;left s[i];right left;}}if(max num) max num;if(right ! s[s.Length - 1]) max 1;return max;}}判断right ! s[i]只能知道当前字符和上一个字符是否不同一旦出现abca这种隔位重复它完全检测不到导致num错误累加。然后发现扫不到最后一个寻思打个补丁然后更乱了。。。可能也是闲的....尝试了一两个小时没有发现保持char指针和扫描的解法所以先放这里也许以后能解。错误尝试二字典记录最后位置排序找连续索引把每个字符的最新出现位置存进字典然后对这些位置排序找到最长的连续递增索引段长度就是最长无重复子串的长度。通过“排序”和“连续递增”来事后拼凑“窗口”而不是在遍历过程中实时维护窗口的合法性。public class Solution { public int LengthOfLongestSubstring(string s) { Dictionarychar, int dict new Dictionarychar, int(); for (int i 0; i s.Length; i) { char c s[i]; if (dict.ContainsKey(c)) dict[c] i; // 保留最后一次出现位置 else dict.Add(c, i); } if (dict.Count 0) return 0; Listint indices dict.Values.ToList(); indices.Sort(); int maxLen 1, curLen 1; for (int i 1; i indices.Count; i) { if (indices[i] indices[i - 1] 1) curLen; else { maxLen Math.Max(maxLen, curLen); curLen 1; } } maxLen Math.Max(maxLen, curLen); return maxLen; } }思路的出发点是“所有不重复字符的最后出现索引如果能连成连续序列就代表一个无重复子串”。但事实上一个无重复子串中某个字符可能出现多次而字典只保留最后一次完全打乱了顺序关系如果可以实时更新这个长度也许可以解决。正确解法滑动窗口 哈希集用left和right两个整数指针维护一个窗口哈希集存储当前窗口内的字符。public class Solution { public int LengthOfLongestSubstring(string s) { if (s null) return 0; int maxLen 0; int left 0; var set new HashSetchar(); for (int right 0; right s.Length; right) { while (set.Contains(s[right])) { set.Remove(s[left]); left; } set.Add(s[right]); maxLen Math.Max(maxLen, right - left 1); } return maxLen; } }备注由于哈希表还不熟练开始准备用字典删除键值对的方式但是后来发现哈希表更简洁一些