题目描述
思路解析
一句话答案：LeetCode 609 系统中的重复文件用哈希分组：把每份内容当 key、完整路径进桶，最后挑出文件数 ＞1 的桶就是一组重复。时间 O(N)、空间 O(N)。
什么样的两个文件，在这题里才算重复
给一列目录信息 paths，每条形如「目录 文件名1(内容1) 文件名2(内容2) …」，括号里是文件内容。要把内容相同的文件按组返回，每组给出完整路径「目录/文件名」，组间与组内顺序随意。判重只认内容，文件名、目录不同都没关系。题面 paths=["root/a 1.txt(abcd) 2.txt(efgh)","root/c 3.txt(abcd)"] 的答案是 [["root/a/1.txt","root/c/3.txt"]]，两文件内容同为 abcd。
把每两个文件掏出来两两比一遍，得比多少次
先把所有目录信息拍平，设一共 m 个文件、每份内容平均 L 个字符。要判重，一种做法是两两配对、逐对比内容，相同就归一组。可两两配对要比 m·(m−1)/2 次，每次还得逐字符比两份内容，时间 O(m²·L)。文件一多，这种平方级别的对撞就拖不动了。
与其两两对撞，不如让内容相同的文件自己聚到一起
换种存法就能绕开两两比较。开一张哈希表，按 key 直接定位、查在不在几乎不花时间，把「文件内容」当 key、把这份内容名下的「完整路径」串成列表当值。遍历每个文件，拿内容去表里找桶：第一次出现就新开一个桶，出现过就把当前路径追加进老桶。内容相同的文件都落进同一个桶。key 必须是内容，绝不能用文件名——名字不同内容照样可能相同。
从一条串里，怎么抠出路径和内容再归桶
每条目录信息按空格切开：第一段是目录 root，后面每段都是「文件名(内容)」。对每段找到左括号，前面是文件名 name、括号里是内容 content——末尾那个右括号要去掉。把 root+"/"+name 拼成完整路径，追加到 groups[content] 桶里。全部归完后扫一遍所有桶：装了不止一个文件（长度 ＞1）的就是一组重复，收进答案；只装一个的跳过。
顺着题面这两条目录信息，一步步归桶
起手 groups 空。第一条目录 root/a：1.txt(abcd) 取出 content=abcd，root/a/1.txt 进 abcd 桶；2.txt(efgh) 取出 content=efgh，root/a/2.txt 进 efgh 桶。第二条目录 root/c：3.txt(abcd) 取出 content=abcd，root/c/3.txt 也进 abcd 桶。归完 abcd 桶两条、efgh 桶一条。扫桶：abcd 长度 2 ＞1 收进答案，efgh 长度 1 跳过。最终答案 [["root/a/1.txt","root/c/3.txt"]]。
key 截内容时带上右括号，同内容文件就进不了一个桶
归桶时每个字符只解析一次、入桶是常数操作，时间 O(N)，N 是所有路径与内容的总字符数；哈希表每条路径存一份，空间 O(N)。截内容时若把右括号也带进 key，abcd 和 abcd) 成了两个不同的 key，本该同桶的文件被拆散、答案少一组。还有别忘过滤只装一个文件的桶，否则单文件桶也被当「组」吐出来。边界先想清——内容全不同时返回空列表；同目录两文件内容相同、或不同目录不同文件名内容相同，都算一组重复。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这套「内容当 key、路径进桶、最后挑 ≥2 的桶」，下面每一帧都在套它。
一共 5 条目录信息，拍平后是 6 个文件。桶现在是空的，等着内容相同的文件落进同一个桶。
先看拆一个文件的招式:找到左括号，前面是文件名，括号里是内容。再把目录拼上文件名，就得到完整路径 root/a/1.txt。下面对每个文件都这么拆。
解析出第 1 个文件 root/a/1.txt，内容是 abcd。这是个没见过的新内容，下一帧给它开一个新桶。
root/a/1.txt 进了 0 号桶（内容 abcd），这个桶现在有 1 个文件。内容一样的文件，会一直往同一个桶里堆。
解析出第 2 个文件 root/a/2.txt，内容是 efgh。这是个没见过的新内容，下一帧给它开一个新桶。
root/a/2.txt 进了 1 号桶（内容 efgh），这个桶现在有 1 个文件。内容一样的文件，会一直往同一个桶里堆。
解析出第 3 个文件 root/c/3.txt，内容是 abcd。这个内容之前出现过，对应的桶亮起来了，下一帧把当前路径也丢进去。
root/c/3.txt 进了 0 号桶（内容 abcd），这个桶现在有 2 个文件。内容一样的文件，会一直往同一个桶里堆。
解析出第 4 个文件 root/c/d/4.txt，内容是 efgh。这个内容之前出现过，对应的桶亮起来了，下一帧把当前路径也丢进去。
root/c/d/4.txt 进了 1 号桶（内容 efgh），这个桶现在有 2 个文件。内容一样的文件，会一直往同一个桶里堆。
解析出第 5 个文件 root/4.txt，内容是 efgh。这个内容之前出现过，对应的桶亮起来了，下一帧把当前路径也丢进去。
root/4.txt 进了 1 号桶（内容 efgh），这个桶现在有 3 个文件。内容一样的文件，会一直往同一个桶里堆。
解析出第 6 个文件 root/e/5.txt，内容是 zzzz。这是个没见过的新内容，下一帧给它开一个新桶。
root/e/5.txt 进了 2 号桶（内容 zzzz），这个桶现在有 1 个文件。内容一样的文件，会一直往同一个桶里堆。
6 个文件都归桶了。可以看到 abcd 桶和 efgh 桶各装了好几个路径，zzzz 桶只有一个。接下来就看哪些桶里装了不止一个。
归桶完成，现在从头到尾扫每个桶。判定规则很简单:桶里装了至少两个文件，这一桶就是一组重复;只装了一个的，跳过。
看 0 号桶，内容 abcd，里面有 2 个文件:root/a/1.txt、root/c/3.txt。数量到了 2 个，这就是一组重复文件，收进答案。
看 1 号桶，内容 efgh，里面有 3 个文件:root/a/2.txt、root/c/d/4.txt、root/4.txt。数量到了 2 个，这就是一组重复文件，收进答案。
看 2 号桶，内容 zzzz，里面只有 1 个文件 root/e/5.txt。孤零零一个，凑不成重复组，跳过它。
扫完三个桶，桶 0 和桶 1 都满足条件，一共 2 组重复文件;zzzz 那桶被跳过。
最终答案是这 2 组:root/a/1.txt、root/c/3.txt 和 root/a/2.txt、root/c/d/4.txt、root/4.txt。每一组里的文件内容都完全相同，正是题目要找的重复文件。
边界先想清:内容全不同为空、单文件为空、同目录同内容也能组成重复。
面试追问聚焦工程化:大文件用哈希摘要省内存，再逐字节比对防误报。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *from string import *from operator import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def findDuplicate(self, paths: List[str]) -> List[List[str]]: groups = defaultdict(list) for entry in paths: parts = entry.split() root = parts[0] for file in parts[1:]: name, rest = file.split("(", 1) content = rest[:-1] groups[content].append(root + "/" + name) ans = [sorted(v) for v in groups.values() if len(v) > 1] ans.sort() return ans复杂度
- 归桶：O(N)，N 为所有文件路径与内容的总字符数:解析每个字符各一次，按内容哈希入桶是常数操作
- 排序：另算，参考代码为输出稳定额外对组内路径、组间顺序排序，按路径数量与字符串比较成本计;排序不是本题必需步骤(题目说顺序任意)
- 空间：O(N)，哈希表把每条路径都存了一份
易错点
面试追问把动画讲成自己的话
追问如果文件内容非常大（GB 级别），还能直接拿内容当 key 吗？
追问如何确保你找出的重复不是误报？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
图像重叠
LeetCode 835 · 中等 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题