LeetCode 3：无重复字符最长子串中set()的作用及为何不用列表？

在这个最长无重复子串的滑动窗口算法里，选择set()而非列表[]，核心原因是两种数据结构的操作时间复杂度差异直接影响算法效率，具体看这几个关键操作：

• 查找操作（s[r] in charSet）：
  set基于哈希表实现，判断元素是否存在的平均时间复杂度是O(1)，能瞬间定位到目标字符；而列表的in操作需要遍历整个列表，时间复杂度是O(n)。随着滑动窗口的扩大，列表的查找耗时会越来越高，最终让整个算法的时间复杂度从O(n)退化到O(n²)。

• 删除操作（charSet.remove(s[l])）：
  set的remove操作同样是O(1)平均时间，哈希表可以直接定位到要删除的元素并移除；而列表的remove不仅要先遍历找到元素位置（O(n)），还要移动后续元素填补空缺（O(n)），两步加起来耗时极高，会拖慢整个滑动窗口的收缩过程。

• 添加操作的差异可以忽略：
  set的add和列表的append都是O(1)平均时间，这部分两者表现差不多，但前面两个核心操作的效率差距才是选择set的关键。

拿示例输入s = "abcabcbb"来说：当右指针走到第二个a时，用set能立刻查到a已存在，然后快速删除左指针指向的第一个a；如果用列表，要先遍历整个["a","b","c"]找到a，再删除它，这个过程的耗时会随着窗口长度增加而显著上升。

内容的提问来源于stack exchange，提问作者Chanhyuk M