给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
1.滑动窗口法，个人理解就基本上类似栈的原理，只是在将元素剔除出当前序列时是有选择的，在每次有元素进入序列时，寻找是否有与当前元素相同的元素在序列中，如有就记录当前长度，然后将开头到与当前元素相同元素的位置所有元素剔除
List： 执行用时：96 ms 内存消耗：24.9 MB 时间复杂度：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. 头到尾滑一遍，遇到重复的就去头部的一位，每次滑动就保存一下长度，最后返回最大长度
Queue：执行用时：128 ms 内存消耗：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.子串不停的加长，每加一个字符，就进行子串内部的对比，如果发现有重复的，则判断当前是否为最大值，并以发现的位置+1做为新的起点。这里要注意的是有重复时，end表示已重复的位置，因此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;
}
