题目描述
思路解析动画文字版
记住这套「内容当 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题