LeetCode.3-无重复字符的最长子串

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

示例 1:

输入: “abcabcbb”

输出: 3

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

示例 2:

输入: “bbbbb”

输出: 1

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

示例 3:

输入: “pwwkew”

输出: 3

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

请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

C#语言实现

方法一：暴力法

public int LengthOfLongestSubstring(string str)
{
	if (str == "") return 0;
	int maxLength = 1;
	for (int i = 0; i <= str.Length - maxLength; i++)
	{
		List<char> charList = new List<char>();
		for (int j = i; j < str.Length && charList.IndexOf(str[j]) == -1; j++)
		{
			charList.Add(str[j]);
		}
		if (charList.Count > maxLength)
		{
			maxLength = charList.Count;
		}
	}
	return maxLength;
}
           

方法二：滑动窗口

public static int LengthOfLongestSubstring1(string str)
{
    int i = 0, j = 0, count = 0;
    //定义一个集合存储不重复的子串字符
    List<char> charList = new List<char>();
    while (i < str.Length && j < str.Length)
    {
        //如果存在重复字符，则删除集合第一个元素
        if (charList.IndexOf(str[j]) != -1)
        {
            charList.Remove(str[i++]);
            continue;
        }
        //添加新字符组成不重复子串
        charList.Add(str[j++]);
        if (charList.Count > count) count = charList.Count;//charList.Count和j-i的值是一样的
    }
    return count;
}
           

方法三：双指针法

public static int LengthOfLongestSubstring(string str)
{
    int count = 0;
    //定义一个字典存储每个字符及索引
    Dictionary<char, int> dic = new Dictionary<char, int>();
    for (int i = 0, j = 0; i < str.Length; i++)
    {
        //又找到了一样的字符
        if (dic.ContainsKey(str[i]))
        {
            //如果之前该字符的索引大于或等于j，
            //那么要将j的值改成重复字符之前的索引+1，
            //表示新的不重复子串的头索引
            if (dic[str[i]] >= j) j = dic[str[i]] + 1;
        }
        dic[str[i]] = i;//添加键值对或修改字符索引
        if (i - j + 1 > count) count = i - j + 1;//计算长度，i和j分别表示头索引和尾索引
    }
    return count;
}