算法:求字符串不重复字符最大长度
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
算法解析
两次循环遍历。父循环从头i开始,子循环从i+1开始,找出从0开如的每个子串的最大长度
通过建立Hashset集合把截取不同的子串添加到集合中,当有重复时,结果添加,通过j-i找到当次循环最大长度。和上次的最大长度比较,取最大值 。
该算法时间复杂变为O(^3)
public class Solution
{
public int lengthOfLongestSubstring(String s)
{
int n = s.Length;
int ans = 0;
//j-i 表示当前子循环的最长子串长度。和上一次的ans比较,取最大值
for (int i = 0; i < n; i++)
for (int j = i + 1; j <= n; j++)
if (allUnique(s, i, j)) ans = Math.Max(ans, j - i);
return ans;
}
public bool allUnique(String s, int start, int end)
{
HashSet<string> s1 = new HashSet<string>();
for(int i=start;i<end;i++)
{
string c = s.Substring(i,1);
if (s1.Contains(c)) return false;
s1.Add(c);
}
return true;
}
}
测试调用
private static void Main(string[] args)
{
string s = "abcabcbb";
int result = new Solution().lengthOfLongestSubstring(s);
Console.WriteLine(result); //结果为3
Console.ReadKey();
}
还不快抢沙发