没有重复字符的最长子字符串-需要了解给定C#解决方案的算法

Question

问题：没有重复字符的最长子字符串。

我有这个解决方案。但我对DSA没有太多的理论知识。试图了解它属于哪种算法，它会比"滑动窗口"方法更有效吗。根据我的理解，时间复杂性是o(n(。空间的复杂性是什么？如有任何帮助/指导，我们将不胜感激。谢谢

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

List<char> list = new List<char>();
int output = 0;

foreach(char c in s)
{
if(list.Contains(c))
{
if(list.Count > output)
output=list.Count;
int index = list.IndexOf(c);
list.RemoveRange(0,index+1);
list.Add(c);
}
else
{
list.Add(c);
}
}

return list.Count > output ? list.Count : output;
}
}

Answer 1

解决方案的内存复杂度为O(a((我不计算s字符串大小-在理想情况下，可能是生成器(，悲观时间复杂度为0(a*n(，其中：

n——s输入字符串的长度

a-字母大小|A|

对于多次重复整个字母表的s：

s = "abcd...xyzabcd...xyzabcd...xyz"

在第一次a迭代之后，列表大小为a，并且它包含每个字母。

然后，对于每个连续迭代，我们移除第一个元素，这意味着所有元素都必须移动——这个操作的成本是a-1。

我们最终得到O((n-a(*(a-1((=O(a*n(。

解决方案可能是使用LinkedList，但正如@maraca在评论中提到的那样-包含悲观复杂性也是O(L(，其中L是列表长度，我们再次得到很少清空list的s的O(a*n(。

如何获得真正的O(n(？

正如注释所建议的那样，使用HashMap来存储上次看到元素的索引。在处理数组时更新索引。将输出计算为当前位置和上次看到的索引之间的差(如果小于当前长度(。

你也可以说，对于a-z字母表，哈希算法的常数大于a(24(，无论哪种方式，它都是O(n(。需要真实世界的测试时间示例：D