企业官网建设流程全解析

刷题刷到这个系列的第四篇，我觉得是时候认真聊聊一个“看起来很简单、实际上经常被用错”的数据结构——Set。在很多人的印象里，Set就是用来去重的：数组转成Set，再转回来，重复项没了，完事。但在LeetCode的场景里，Set能做的不只是去重这一件事。它能在O(1)复杂度里回答“这个元素之前见过吗”，它能做集合的交集、并集、差集运算，它还能配合双指针做滑动窗口的判重。这篇文章我会把Set相关的题目从“该不该用”到“怎么用”完整过一遍，内容包括高频场景归纳、三道完整实操题、底层原理，以及我踩过的一些坑。适合刚学完基础数据结构、准备系统刷题的人，也适合面试前想快速把Set相关题目过一遍的人。

1. 先建立直觉：Set到底在解决什么问题？

1.1 Set三个不可替代的核心能力

先想清楚一件事：数组也能存储一堆元素，为什么还要用Set？因为Set有三个数组很难同时满足的特性。

第一，存在性查询是O(1)。一个元素在不在集合里，哈希表结构让它可以在常数时间内回答。数组想判断一个元素在不在，要么遍历O(n)，要么先排序再二分O(log n)，都慢。第二，它天然去重。你不断往Set里加数据，重复的自动被忽略，适合处理“出现过没”“重复没”这类问题。第三，集合运算非常自然。求两个数组的交集，直接setA & setB就出来了，不需要自己写两层循环。

这三个能力，对应了刷题时绝大多数Set使用场景。你可以这样记：看到“去重”“是否出现过”“交集差集”“判断重复”这些词，脑子里第一反应就该是Set。

1.2 快速判断一道题是否该用Set

我在刷题过程中总结出两个比较准的信号。第一个信号是问题里出现了“是否重复”或“是否已经见过”。比如判断数组里有没有重复元素、判断链表有没有环、判断一个数是不是快乐数，本质都是“之前见过没”。第二个信号是出现了“交集、并集、差集、子集”这类集合词汇，而且对顺序和数量没有严格要求。

但要注意，题目里出现这些词不代表一定用Set。比如“求两个数组的交集”如果要求每个元素出现的次数和原数组一致，那要用Counter（哈希表），因为Set会丢次数信息。判断标准就一句话：只要只关心“有还是没有”，而不关心“有多少个”“在哪个位置”，优先用Set。

1.3 什么时候一定要避开Set

有几种情况用了Set反而走弯路。

第一种是需要保持顺序的场景。字符串去重后要求保留第一次出现的顺序，直接转Set再转回来顺序就乱了，这时候应该用遍历+一个已访问标记（可以是另一个Set，但输出用列表）。第二种是需要计数的场景。想统计字符出现次数，用Set只能记录“出现过”，不能记录“出现了3次”，应该用哈希表。第三种是元素本身不可哈希，比如想把一个列表对象放入Set，Python直接报错，这种情况要么转换成元组要么重新设计数据结构。

2. 高频场景拆解：为什么这些题都藏在Set里

2.1 去重与存在性检查：从217到219

LeetCode 217题“存在重复元素”是Set最经典的入门题。给一个数组，判断是否存在两个相同的元素。最暴力的做法是双层循环，O(n^2)。另一个思路是先排序再检查相邻元素，O(n log n)。但用Set的话，一次遍历就搞定，边遍历边往Set里加，只要当前元素在Set里已存在，直接返回True。

219题是它的进阶版，要求重复元素的下标距离不超过k。这时候光靠Set不够，因为你还需要记录下标，所以要用哈希表（字典）来存“元素->最后出现下标”。这个变化在面试里经常出现，核心思想不变：依然是边遍历边记录“见没见过”，只是把Set换成了Map，为了额外存位置信息。记住这个套路，遇到类似“重复且带距离限制”的题，你就能想到从Set升级成Map。

2.2 集合运算：求数组交集

LeetCode 349题“两个数组的交集”，要求返回两个数组中共同出现的元素，且结果不能重复。这题如果不知道Set，会写得很痛苦：两个循环遍历、还要去重、还要判断谁在谁里面。但用Set的集合运算，一行核心代码就能表达核心逻辑。

背后的逻辑是，集合交集运算就是把两个Set中的共有元素筛选出来，底层是哈希查找，性能很好。我在面试中问过不少候选人，很多人知道Python有&运算，但不知道Java里对应的是retainAll方法，或者不清楚C++里要自己遍历小集合然后查大集合。这说明大家普遍只记住了自己常用语言的API，而对“集合运算”本身是干什么的理解不深。建议你在理解层面记住交集、并集、差集的概念，再查一下所用语言的对应写法。

2.3 检测循环：链表中判环、快乐数

环形链表检测是面试高频题。给定一个链表，判断有没有环。除了经典的快慢指针，很多人的第一反应是用Set记录遍历过的节点：每到一个节点，先看它是否已经在Set里，在就说明有环，否则加入Set继续走。这个解法的好处是直观、不容易错，代价是O(n)的空间。快慢指针虽然空间O(1)，但思路需要练习才能形成条件反射。

同样的模式还出现在快乐数问题里。快乐数的计算过程就是不断用各位数字平方和生成新数，如果某个数重复出现，说明进入了循环。这本质和“链表有没有环”一模一样，甚至不需要真的构造链表，只用一个Set记录出现过的数就行。刷完这两题你会发现，很多“判断会不会循环”“会不会回到之前状态”的题，套路都是同一个：一个Set记录历史状态。

2.4 滑动窗口与Set的组合拳

滑动窗口是字符串题里的常见套路，而Set在其中经常扮演“窗口内元素集合”的角色。典型题目就是“无重复字符的最长子串”。窗口右侧不断扩展，每次遇到新字符，把字符加进Set；如果遇到重复字符，就往右收缩左边界，把左边移出窗口的字符从Set里删掉。这个过程里，Set维护的是“当前窗口有哪些字符”。

这个场景和前面去重不一样的地方在于，Set不仅要做存在性判断，还要支持“删除指定元素”。你需要在收缩左边界时把left位置的字符从Set中移除，同时left向右移动。很多初学者在这里会漏掉删除操作，导致窗口内Set永远带着已离开的字符，结果永远重复。这个细节我放在后面实操部分重点讲。

3. 实操演示：三道经典题目从读题到AC

3.1 存在重复元素：新手第一课的完整走读

题目如下：给定一个整数数组nums，如果任一值在数组中出现至少两次，返回true；如果数组中每个元素互不相同，返回false。

我第一次做这题的时候，第一反应是排序后看相邻元素，虽然能过，但完全没有体现出对数据结构的理解。后来我强迫自己每次先思考“有没有可能用哈希结构”。

用Set的写法非常清爽：

class Solution: def containsDuplicate(self, nums: List[int]) -> bool: seen = set() for num in nums: if num in seen: return True seen.add(num) return False

这段代码的时间复杂度是O(n)，空间复杂度是O(n)。你甚至可以更简洁地写成return len(nums) != len(set(nums))，一行搞定。但我在面试里不太建议只写一行，因为面试官通常想听你讲清楚“set的查找为什么是O(1)”，也想知道你理解哈希冲突。先把遍历版本写清楚，再补一句“其实也可以用长度对比，但本质上利用的是Set去重能力”，会显得你更有深度。

因为篇幅原因，具体分级内容见后续完整内容。

下面继续：

我在这题上踩过一个低级坑：直接写了set(nums)然后再去遍历原数组判断，表面上没问题，但多了一次完整的数组转Set操作，虽然复杂度量级没变，常数大了不少。遇到数据量大的用例，性能差距就很明显了。养成好习惯：能一次遍历解决的去重类问题，不要先转集合再遍历。

3.2 两个数组的交集：用集合运算还是用双指针

题目要求：给定两个数组，返回它们的交集。输出结果中的每个元素是唯一的，不考虑输出顺序。

最简单的写法：

class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: return list(set(nums1) & set(nums2))

但这题其实有很多隐藏考点。第一，set(nums1)和set(nums2)会先各自去重，然后&运算求出交集，最后list()转回列表。整个过程非常好理解。第二，面试官跟进的问题通常是：如果两个数组已经排好序，能不能不用Set？当然可以，用双指针，一个指针分别移动，遇到相同元素记录后同时移动，时间复杂度O(m+n)，空间O(1)。第三，如果要求交集中的元素出现次数和原数组保持一致，那就要用Counter。

我建议你把这三种解法都准备好：哈希集合版本回答“标准思路”，排序双指针版本回答“优化空间”，哈希表版本回答“进阶变体”。一道题能讲出三个层次，在面试里的效果完全不同。刷题不是背代码，而是把一个题目的不同约束条件都看清楚：不需要计数就用Set，需要计数就用Counter。

3.3 最长无重复字符子串：Set在滑动窗口里的最佳舞台

题目描述：给定一个字符串，找出其中不含有重复字符的最长子串的长度。

这题的Set写法是滑动窗口的经典模板，我建议直接背下来，同时理解每一步为什么这么做：

class Solution: def lengthOfLongestSubstring(self, s: str) -> int: seen = set() left = 0 ans = 0 for right, ch in enumerate(s): while ch in seen: seen.remove(s[left]) left += 1 seen.add(ch) ans = max(ans, right - left + 1) return ans

关键点在于while ch in seen这个循环。右指针指向的新字符已经存在于窗口里了，说明窗口内存在重复。那为什么要循环移除而不是只移一次？因为重复字符可能在窗口的中间位置，你光把最左边的字符移走，可能还是和ch重复，所以必须一直移，直到窗口里不再有ch为止。

seen.remove(s[left])这个操作还需要注意：必须用left指向的字符来删，而不是直接seen.remove(ch)。如果直接删ch，你删掉的是那个重复字符本身，窗口左边界却只往右挪了一格，窗口数据就全乱了。这个错误我犯过不止一次，后来养成的习惯是：窗口滑动时，哪边的元素离开窗口，就从集合里删哪个元素。

时间复杂度和空间复杂度都是O(n)，其中n是字符串长度。空间复杂度精确来说是O(min(n, 字符集大小))，因为Set里最多存字符集大小的元素。

另一种优化方案是用哈希表记录每个字符最近一次出现的下标，让left可以直接跳到重复位置+1，而不用while逐个移。但在面试里，我建议先写Set版本，逻辑更直观，等面试官追问“能不能优化”时再升级成Map版本。能把基础版本讲干净，比一上来就写花活稳得多。

4. Set的底层原理与真正的坑

4.1 为什么能O(1)：哈希表不是免费午餐

Set在主流语言里的底层实现都是哈希表。Python的Set底层是哈希表加开放寻址，Java的HashSet底层是HashMap，C++的unordered_set底层是哈希桶。哈希表能把一个元素通过哈希函数映射到一个固定位置，所以查找时不需要跟所有元素比较，平均复杂度是O(1)。

但“平均O(1)”不等于“永远O(1)”。如果哈希函数不好，或者元素大量冲突，查找会退化成O(n)。刷题时你通常不需要关心这一点，因为语言内置的哈希函数已经针对常见类型做了充分优化。你需要知道的是：自定义类放入Set时要保证__hash__和__eq__行为一致，否则大概率会出现诡异bug。比如，两个对象内容是相等的，但哈希值不同，Set就会把两个“本质相同”的对象当成不同元素存进去。

我建议刷题时如果涉及到自定义对象（比如二维坐标点、状态快照），要么让系统默认的对象哈希行为保持不变，要么自己把对象转成元组再放进Set，后者更省心。

4.2 不可哈希对象与frozenset

这是Python刷题新手最容易踩的坑之一。直接执行set()放入列表会报错：TypeError: unhashable type: 'list'。原因很简单，Set要求元素不可变，否则元素放进集合后内容一变，它对应的哈希位置就失效了，整个结构就乱了。列表是可变的，所以不能进Set。

解决方案有两类。第一类是把列表转成元组再放进Set，比如你要判断一个数组出现了哪些不同形态，就让形状信息以元组形式存在Set里。第二类是用frozenset，它相当于不可变的Set，可以放进别的Set里，在处理集合的集合时非常好用。比如你要求两个数组之间所有可能的子集组合，又想去重，就可以把每个子集转成frozenset存进外层的Set。

4.3 遍历时修改集合：经典运行时报错

一个很典型的现象：你在遍历一个Set，同时在循环体里往Set里添加或删除元素，程序直接抛RuntimeError: Set changed size during iteration。我在刷“根据条件动态扩展集合”这类题目时经常遇到。

出现这个报错的原因很好理解：迭代器在遍历过程中依赖集合的内部状态，你在中途改动它，迭代器根本不知道下一个元素去哪找，于是直接拒绝继续。解决办法有两个。一是先把要处理的内容用list(set(...))复制出来，遍历列表，修改原集合。二是按照“收集后统一变更”的思路，先在循环里把要加的元素放进一个临时列表，循环结束后再用update批量添加。

这个习惯不但能避免报错，还能让代码逻辑更清晰。我当时做一道“把满足条件的元素全部删掉”的题，边遍历边删，死活调不对，后来改成“先筛出要删的，再统一remove”，一次就过了。

5. 刷Set题的常见错误与排查速查

5.1 一套常见的“错法”清单

我整理了这几道题之外最常见的错误，方便你自查：

这张表里的每一条我都见过真实案例。其中最隐蔽的是“字符串去重后顺序乱了”这条，因为很多新人觉得“Set能去重，那字符串去重不是一行代码吗”，结果输出顺序和预期差很远，其实题目往往要求保留首次出现顺序。遇到这种题，还是老老实实遍历一遍，用Set做“是否已出现过”的判断，输出存到一个列表里。

5.2 不同语言里的Set，这几点必须分清楚

刷题时不同语法的差异看起来是小事，但面试写代码时很容易卡壳。

Python里要记住frozenset的存在，以及set本身没有下标访问。Java里HashSet是最常用的，但它不保证顺序；LinkedHashSet保插入顺序；TreeSet底层是红黑树，元素自动排序，查找是O(log n)。如果题目要求“按字典序输出结果”，TreeSet就有用了。

C++里unordered_set是哈希表，平均O(1)但无序；set底层是红黑树，O(log n)查找，有序。刷题时默认用unordered_set，除非题目要求输出有序结果。

还有一个容易忽略的点：Python Set要求元素可哈希，Java HashSet要求元素正确重写equals和hashCode，C++ unordered_set要求元素类型有哈希函数支持。遇到自定义结构体、自定义对象时，不同语言的优雅程度完全不同。我在做图相关的题目时，经常要把“边的信息”放进Set去重，Python用tuple很方便，Java就要考虑自定义对象的equals/hashCode。

5.3 我刷Set题时总结的三个小习惯

最后分享三个我自己的习惯，第一个是：做完一道题后，在代码注释里写一行“为什么用Set不用List/Map”。这行注释看起来多余，但我每次回头看代码时都受益。它逼着你梳理清楚数据结构的边界。第二个习惯是：遇到“无重复”“是否出现”这类描述，先把题目归类到Set这个抽屉里，再检查有没有额外需求（计数、顺序、距离），再决定升级成Map还是保持Set。第三个习惯是：刷完题目先看官方题解和讨论区，看别人用了什么更精巧的集合操作。比如349题，有人用一行set(nums1) & set(nums2)，有人用双指针，没有哪个一定错，看你更擅长哪种。多对比几次，你就能形成自己的刷题决策表。

我个人在实际操作中的体会是，Set类题目是整个刷题过程中“性价比”很高的一类：代码量不大，思路清晰，正确率高，但前提是你真的理解它为什么快、它有哪些限制。如果你现在刷到这类题经常卡壳，别急，先把这篇文章里的三道实操题手写三遍，再自己找三五道同类题目练手。等你能在不同语言里准确选择合适的Set变体，这块基本就过关了。最后再分享一个小技巧：把Set的常用操作、复杂度、坑写在笔记本首页，每次刷题前扫一眼，坚持两周，你对Set的敏感度会有明显提升。