C#算法之无重复字符的最长子串

题目

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

示例 1:

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

示例 2:

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

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。

要注意字符串为空、变量为null、字符串长度 Length = 1 等情况。

测试实例

输入
" "
"au"
"abcabcbb"
"bbbbb"
"pwwkew"
"aab"

预期结果分别是 1,2,3,1,3,2

代码格式模板

public class Solution {
   public int LengthOfLongestSubstring(string s) {

}
}

笔者的代码仅供参考

使用最笨的方式，200ms左右

public class Solution {
   public int LengthOfLongestSubstring(string s) {
                   if (s == null || s == "")
               return 0;

char[] a = s.ToCharArray();      //字符串转为字符数组
           int start = 0;                   //区间开始位置
           int stop = 0;                    //区间结束位置
           int newMax = 1;                   //当前区间数
           int max = 1;                     //区间最大个数

for (stop = 1; stop < a.Length; stop++)   //每次向后移动一位
           {
               bool b = false;                       //是否存在重复
               for (int i = start; i < stop; i++)  //检查当前元素在区间是否有相同值
               {
                   if (a[stop] == a[i])        //如果stop+1位在区间找到相同的字符
                   {
                       char ls = a[stop];
                       if (newMax > max) max = newMax;
                       start = i + 1;              //区间开始位置重置
                       newMax = stop - start + 1;
                       b = true;            
                       break;
                   }
               }
               if (b == false)
                   newMax += 1;
           }
           if (newMax > max) max = newMax;
           return max;
   }
}

完整测试代码(控制台)

using System;

namespace ConsoleApp1
{
   public class Testa
   {
       public int LengthOfLongestSubstring(string s)
       {
           if (s == null || s == "")
               return 0;

char[] a = s.ToCharArray();      //字符串转为字符数组
           int start = 0;                   //区间开始位置
           int stop = 0;                    //区间结束位置
           int newMax = 1;                   //当前区间数
           int max = 1;                     //区间最大个数

for (stop = 1; stop < a.Length; stop++)   //每次向后移动一位
           {
               bool b = false;                       //是否存在重复
               for (int i = start; i < stop; i++)  //检查当前元素在区间是否有相同值
               {
                   if (a[stop] == a[i])        //如果stop+1位在区间找到相同的字符
                   {
                       char ls = a[stop];
                       if (newMax > max) max = newMax;
                       start = i + 1;              //区间开始位置重置
                       newMax = stop - start + 1;      //重新设置区间数
                       b = true;            
                       break;
                   }
               }
               if (b == false)             ////没有重新设置区间数时加1
                   newMax += 1;
           }
           if (newMax > max) max = newMax;
           return max;
       }
   }
   class Program
   {

static void Main(string[] args)
       {
           Testa t1 = new Testa();                                     //正确结果
           Console.WriteLine(t1.LengthOfLongestSubstring(" "));        //1
           Console.WriteLine(t1.LengthOfLongestSubstring("au"));       //2
           Console.WriteLine(t1.LengthOfLongestSubstring("abcabcbb")); //3
           Console.WriteLine(t1.LengthOfLongestSubstring("bbbbb"));    //1
           Console.WriteLine(t1.LengthOfLongestSubstring("pwwkew"));   //3
           Console.WriteLine(t1.LengthOfLongestSubstring("aab"));      //2
           Console.ReadKey();
       }
   }
}

使用哈希集合，速度更快，100ms-150ms

public int LengthOfLongestSubstring(string s)
       {
           int n = s.Length;
           HashSet<char> set = new HashSet<char>();        //集合
           int ans = 0, start = 0, stop = 0;               //ans为字符串长度，starp区间起点，stop区间终点
           while (start < n && stop < n)
           {
               // try to extend the range [i, j]
               if (!set.Contains(s[stop]))
               {
                   set.Add(s[stop++]);
                   ans = Math.Max(ans, stop - start);
                   //或者ans = ans > (stop - start) ? ans : (stop - start)
               }
               else
               {
                   set.Remove(s[start++]);
               }
           }
           return ans;
       }

完整控制台测试代码

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApp2
{
   public class Solution
   {
       public int LengthOfLongestSubstring(string s)
       {
           int n = s.Length;
           HashSet<char> set = new HashSet<char>();        //集合
           int ans = 0, start = 0, stop = 0;               //ans为字符串长度，starp区间起点，stop区间终点
           while (start < n && stop < n)
           {
               // try to extend the range [i, j]
               if (!set.Contains(s[stop]))
               {
                   set.Add(s[stop++]);
                   ans = Math.Max(ans, stop - start);
                   //或者ans = ans > (stop - start) ? ans : (stop - start)
               }
               else
               {
                   set.Remove(s[start++]);
               }
           }
           return ans;
       }
   }
   class Program
   {
       static void Main(string[] args)
       {

Solution t1 = new Solution();                                     //正确结果
           Console.WriteLine(t1.LengthOfLongestSubstring(" "));        //1
           Console.WriteLine(t1.LengthOfLongestSubstring("au"));       //2
           Console.WriteLine(t1.LengthOfLongestSubstring("abcabcbb")); //3
           Console.WriteLine(t1.LengthOfLongestSubstring("bbbbb"));    //1
           Console.WriteLine(t1.LengthOfLongestSubstring("pwwkew"));   //3
           Console.WriteLine(t1.LengthOfLongestSubstring("aab"));      //2
           Console.ReadKey();
       }
   }
}

来源：https://www.cnblogs.com/whuanle/p/10342416.html