1. 集合是什么1.1 生活中的集合想象你有一个音乐播放列表里面收藏了你喜欢的歌曲。这个播放列表有几个特点没有重复同一首歌不会收藏两次无序排列你不在乎哪首歌在前哪首在后快速查找你能瞬间判断某首歌是否在列表中这就是集合的本质集合Set一种无序、不重复的元素集合基于哈希表实现支持 O(1) 的成员检测。1.2 为什么需要集合# 场景从用户行为日志中提取去重后的用户IDuser_logs[1001,1002,1001,1003,1002,1004,1001]# 用列表去重低效unique_users_list[]foruidinuser_logs:ifuidnotinunique_users_list:# O(n) 查找unique_users_list.append(uid)print(unique_users_list)# [1001, 1002, 1003, 1004]# 时间复杂度O(n²)# 用集合去重高效unique_users_setset(user_logs)# O(n)print(unique_users_set)# {1001, 1002, 1003, 1004}# 时间复杂度O(n)核心优势集合的in操作是O(1)列表是O(n)。数据量越大差距越明显。2. 集合的创建与基本操作2.1 创建集合的四种方式# 方式1花括号注意空{}是字典s1{1,2,3,4,5}print(type(s1))# class set# 方式2set() 构造函数s2set([3,4,5,6,7])# 从列表s3set((1,2,3))# 从元组s4set(hello)# 从字符串 → {h, e, l, o}s5set(range(5))# 从 range → {0, 1, 2, 3, 4}# 方式3集合推导式类似列表推导式s6{x**2forxinrange(10)ifx%20}# {0, 4, 16, 36, 64}# 方式4frozenset不可变集合可作为字典键fsfrozenset([1,2,3])print(type(fs))# class frozenset⚠️重要{}创建的是空字典不是空集合空集合必须用set()。2.2 添加与删除元素s{1,2,3}# ─── 添加元素 ───# add()添加单个元素s.add(4)print(s)# {1, 2, 3, 4}s.add(3)# 添加重复元素无效果print(s)# {1, 2, 3, 4}# update()添加多个元素可迭代对象s.update([5,6])# 添加列表s.update({7,8})# 添加集合s.update((9,10))# 添加元组s.update(ab)# 添加字符串 → 添加 a, bprint(s)# {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, a, b}# ─── 删除元素 ───s{1,2,3,4,5}# remove()删除指定元素不存在则报错s.remove(3)print(s)# {1, 2, 4, 5}# s.remove(10) # KeyError: 10# discard()删除指定元素不存在不报错推荐s.discard(4)# 成功删除s.discard(10)# 静默忽略不报错# pop()随机删除并返回一个元素items.pop()print(f弹出:{item}, 剩余:{s})# clear()清空集合s.clear()print(s)# set()2.3 查询与遍历s{Python,Java,Go,Rust}# 成员检测集合最强功能print(Pythonins)# True ← O(1)print(Cins)# False ← O(1)# 遍历无序forlangins:print(lang)# 输出顺序不确定可能是 Go, Java, Python, Rust...# 长度print(len(s))# 4# 判断空集print(bool(s))# Trueprint(bool(set()))# False3. 集合运算数学之美集合最优雅的地方在于它直接支持数学集合运算。数学符号 vs Python 运算符 A ∪ B (并集) → A | B 或 A.union(B) A ∩ B (交集) → A B 或 A.intersection(B) A - B (差集) → A - B 或 A.difference(B) A △ B (对称差) → A ^ B 或 A.symmetric_difference(B) A ⊆ B (子集) → A B 或 A.issubset(B) A ⊇ B (超集) → A B 或 A.issuperset(B)3.1 并集合并去重frontend{HTML,CSS,JavaScript,React}backend{Python,Java,SQL,JavaScript}# 并集所有技能去重all_skillsfrontend|backendprint(all_skills)# {HTML, CSS, JavaScript, React, Python, Java, SQL}# 等价写法all_skillsfrontend.union(backend)3.2 交集共同元素# 交集前后端都会的技能commonfrontendbackendprint(common)# {JavaScript}# 等价写法commonfrontend.intersection(backend)3.3 差集独有元素# 差集仅前端会的only_frontendfrontend-backendprint(only_frontend)# {HTML, CSS, React}# 差集仅后端会的only_backendbackend-frontendprint(only_backend)# {Python, Java, SQL}# 对称差集仅一方会的不会双方都有的exclusivefrontend^backendprint(exclusive)# {HTML, CSS, React, Python, Java, SQL}3.4 子集与超集skills{Python,SQL,Linux}backend_must{Python,SQL}# 子集判断print(backend_mustskills)# Trueprint(backend_must.issubset(skills))# True# 超集判断print(skillsbackend_must)# Trueprint(skills.issuperset(backend_must))# True# 真子集严格子集print(backend_mustskills)# Trueskills 更大print(skillsskills)# False不是真子集# 不相交判断print({A,B}.isdisjoint({C,D}))# True无共同元素3.5 运算可视化frontend {HTML, CSS, JS, React} backend {Python, Java, SQL, JS} ┌─────────────────────────────┐ │ 并集 frontend | backend │ │ {HTML, CSS, JS, React, │ │ Python, Java, SQL} │ │ ┌───┐ │ │ {JS} │ │ │ │ 交集 │ │ │ │ └───┘ │ │ 仅前端 仅后端 │ │ {HTML,CSS, {Python,Java, │ │ React} SQL} │ └─────────────────────────────┘4. 集合的底层原理4.1 基于哈希表实现Python 的set和dict一样底层都是哈希表Hash Table。哈希表原理 键(key) → 哈希函数 → 哈希值 → 取模 → 数组索引 ↓ ┌─────────┐ │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ └─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┘ │ │ │ │ │ │ None 42 None 17 None 99 查找 42hash(42) % 6 1 → 直接访问索引1 → O(1)4.2 为什么集合元素必须可哈希# ✅ 可哈希元素不可变类型s{1,hello,(1,2),frozenset([3,4])}# ❌ 不可哈希元素可变类型# s {[1, 2]} # TypeError: unhashable type: list# s {{1, 2}} # TypeError: unhashable type: set# s {{a: 1}} # TypeError: unhashable type: dict# 原理哈希值必须稳定可变对象哈希值会变4.3 集合 vs 列表 vs 字典特性列表list集合set字典dict有序性✅ 有序❌ 无序Python 3.7 有序重复元素✅ 允许❌ 不允许❌ 键不允许重复查找速度O(n)O(1)O(1)内存占用小较大哈希表较大适用场景有序序列去重、成员检测键值映射可哈希元素无要求必须可哈希键必须可哈希5. 集合在算法中的应用5.1 两数之和哈希优化版deftwo_sum(nums:list[int],target:int)-list[int]: 用集合/字典优化从 O(n²) 降到 O(n) seenset()fori,numinenumerate(nums):complementtarget-numifcomplementinseen:# O(1) 查找return[nums.index(complement),i]seen.add(num)return[]# 测试print(two_sum([2,7,11,15],9))# [0, 1]print(two_sum([3,2,4],6))# [1, 2]5.2 判断数组是否有重复元素defcontains_duplicate(nums:list[int])-bool:利用集合去重特性returnlen(nums)!len(set(nums))# 测试print(contains_duplicate([1,2,3,4]))# Falseprint(contains_duplicate([1,2,3,3]))# True5.3 寻找两个数组的交集defintersection(nums1:list[int],nums2:list[int])-list[int]: 求两个数组的交集去重 方法1集合运算推荐 returnlist(set(nums1)set(nums2))defintersection_v2(nums1:list[int],nums2:list[int])-list[int]: 方法2遍历较小集合检测是否在另一个集合中 适合一个数组很大一个很小的情况 iflen(nums1)len(nums2):nums1,nums2nums2,nums1# 保证 nums1 较小set2set(nums2)return[xforxinset(nums1)ifxinset2]# 测试print(intersection([1,2,2,1],[2,2]))# [2]print(intersection_v2([4,9,5],[9,4,9,8,4]))# [9, 4]5.4 最长连续序列deflongest_consecutive(nums:list[int])-int: 最长连续序列 思路用集合 O(1) 查找只从序列起点开始计数 时间O(n)空间O(n) num_setset(nums)longest0fornuminnum_set:# 只从序列的起点开始num-1 不在集合中ifnum-1notinnum_set:current_numnum current_streak1whilecurrent_num1innum_set:current_num1current_streak1longestmax(longest,current_streak)returnlongest# 测试print(longest_consecutive([100,4,200,1,3,2]))# 4 ([1,2,3,4])print(longest_consecutive([0,3,7,2,5,8,4,6,0,1]))# 95.5 单词拆分defword_break(s:str,word_dict:list[str])-bool: 判断字符串能否被拆分成字典中的单词 用集合加速查找 word_setset(word_dict)nlen(s)dp[False]*(n1)dp[0]True# 空字符串可被拆分foriinrange(1,n1):forjinrange(i):ifdp[j]ands[j:i]inword_set:# O(1) 查找dp[i]Truebreakreturndp[n]# 测试print(word_break(leetcode,[leet,code]))# Trueprint(word_break(applepenapple,[apple,pen]))# Trueprint(word_break(catsandog,[cats,dog,sand,and,cat]))# False6. 性能对比与最佳实践6.1 成员检测性能对比importtimedefbenchmark():对比列表和集合的成员检测性能# 准备数据n100000datalist(range(n))targetn-1# 最后一个元素最坏情况# 列表查找starttime.time()for_inrange(1000):foundtargetindata# O(n)list_timetime.time()-start# 集合查找data_setset(data)starttime.time()for_inrange(1000):foundtargetindata_set# O(1)set_timetime.time()-startprint(f数据量:{n})print(f列表查找 1000 次:{list_time:.4f}秒)print(f集合查找 1000 次:{set_time:.4f}秒)print(f集合快{list_time/set_time:.0f}倍)benchmark()典型输出数据量: 100000 列表查找 1000 次: 2.3456秒 集合查找 1000 次: 0.0001秒 集合快 23456 倍6.2 去重性能对比importrandomdefdedupe_benchmark():对比不同去重方法的性能data[random.randint(0,10000)for_inrange(100000)]# 方法1列表遍历O(n²)importtime starttime.time()result[]forxindata:ifxnotinresult:result.append(x)t1time.time()-start# 方法2集合去重O(n)starttime.time()resultlist(set(data))t2time.time()-start# 方法3dict.fromkeys保持顺序Python 3.7starttime.time()resultlist(dict.fromkeys(data))t3time.time()-startprint(f列表遍历:{t1:.4f}秒)print(f集合去重:{t2:.4f}秒)print(f字典去重:{t3:.4f}秒)dedupe_benchmark()6.3 最佳实践# ✅ 推荐用法# 1. 快速去重uniquelist(set(original_list))# 2. 成员检测大量查询时ifiteminsome_set:# 比 list 快得多# 3. 集合运算替代循环commonset(a)set(b)# 比双重循环优雅# 4. 过滤重复seenset()foriteminitems:ifitemnotinseen:seen.add(item)process(item)# ❌ 避免用法# 1. 不要依赖集合顺序虽然 Python 3.7 有插入顺序但不保证# 需要有序用 dict.fromkeys() 或 sorted()# 2. 不要存储可变对象# bad_set {[1, 2]} # TypeError# 3. 小数据量没必要转集合# 10个元素的列表in 操作也很快7. 总结7.1 核心要点速查操作方法时间复杂度说明创建set()/{}O(n)空集合用set()添加add()O(1)单个元素添加多个update()O(k)可迭代对象删除remove()/discard()O(1)discard 更安全成员检测inO(1)最强功能并集|/union()O(len(s)len(t))交集/intersection()O(min(len(s),len(t)))差集-/difference()O(len(s))对称差^/symmetric_difference()O(len(s)len(t))7.2 集合使用场景什么时候用集合 ├── 需要去重 │ └── list → set → list ├── 频繁成员检测 │ └── if x in container: 用 set 替代 list ├── 集合运算 │ └── 交集、并集、差集等数学运算 ├── 过滤重复 │ └── 配合 seen 集合记录已处理元素 └── 算法优化 └── 用 O(1) 查找替代 O(n) 查找7.3 与列表、字典的关系┌─────────────┐ │ 可变容器 │ └──────┬──────┘ │ ┌─────────┼─────────┐ │ │ │ ▼ ▼ ▼ list set dict (有序) (无序) (键值对) 可重复 不重复 键不重复 O(n)查找 O(1)查找 O(1)查找