LeeCode_3.无重复字符的最长子串

3. 无重复字符的最长子串难度中等3297给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:

输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:

输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

---

双指针蜗牛算法

public class Solution 
{
    public int LengthOfLongestSubstring(string s) 
    {
        if(s.Length==0) return 0;
        int size = 0;
        for(int i=0;i<s.Length;i++)
        {
            string max = s.Substring(i,1);
            int TempSize = 1;
            for(int j=i+1;j<s.Length;j++)
            {
                string p = s.Substring(j,1);
                if(max.Contains(p)) break;
                max = max + p;
                TempSize++;
            }
            if(TempSize>=size) size=TempSize;
        }
        return size;
    }
}

滑动窗口

利用HashSet

public class Solution 
{
    public int LengthOfLongestSubstring(string s)
    {
        int n = s.Length;
        HashSet<char> set = new HashSet<char>();
        int result = 0;
        int i = 0;
        int j = 0;
        while (i < n && j < n)
        {
            if (set.Contains(s[j]))
            {
                set.Remove(s[i]);
                i++;
            }
            else
            {
                set.Add(s[j]);
                j++;
                result = Math.Max(result, j - i);
            }
        }
        return result;
    }
}

利用字符表

public class Solution 
{
    public int LengthOfLongestSubstring(string s) 
    {
        int max = 0;
        int[] charTable = new int[256];
        int left = 0;
        for (int i = 0; i < s.Length; ++i)
        {
            if (charTable[s[i]] > left)
            {
                if (i - left > max) max = i - left;
                left = charTable[s[i]];
            }
            charTable[s[i]] = i + 1;
        }
        if (s.Length - left > max) max = s.Length - left;
        return max;
    }
}