LeetCode 609. 在系统中查找重复文件

2021-02-20 HGNULB 约 11 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 609. 在系统中查找重复文件

题意分析

给一个字符串数组 paths，每个元素形如 "根目录文件1(内容1) 文件2(内容2) ..."——用空格分隔，第一段是目录路径，之后每一段都是一个「文件名紧跟着一对括号包住的内容」。要求找出所有内容完全相同的文件，把它们的完整路径按组返回；只含一个文件的内容不算重复，不要输出。

判断重复的依据是内容，与文件名和所在目录完全无关。这句话直接决定了数据结构：需要一个「内容 → 该内容对应的所有完整路径」的映射，也就是按内容做分组。

输出要求的是完整路径，格式是 目录 + "/" + 文件名——注意不带括号里的内容。所以解析时必须把每一段拆成文件名和内容两部分，前者拼进路径、后者当作分组的键。

约束方面，输入总字符量是线性规模，而分组本身只需要一趟扫描 + 哈希查找，所以目标复杂度是 $O(L)$（L 为所有输入字符串的总长度）。题目没有暗示任何排序或比较需求，也就排除了「两两比较内容」的 $O(k^2)$ 做法——那不仅慢，而且分组结果还要额外去重。

边界与陷阱：括号内的内容可能包含空格吗？题目保证不会，所以可以放心用空格切分；但文件名和内容都可能包含除空格和括号外的任意字符，因此定位括号必须用「第一个 (」和「最后一个字符是 )」这两个锚点，而不能假设长度。另外某条记录可能只有目录没有文件（parts.length == 1），此时内层循环一次都不进，天然安全。

最后一处容易读漏：只输出组大小大于 1 的分组。所有内容各不相同时应返回空列表而不是一堆单元素组。

题目末尾的追问也值得先想一遍：真实文件系统里内容可能极大，不适合整份读进内存当键——那时应先比长度、再比内容哈希，最后才做逐字节比对。

解法：哈希表按内容分组

核心思路

朴素做法是把所有文件解析出来放进一个列表，然后两两比较内容，相同的归到一组。设文件总数为 k、内容平均长度为 c，代价是 $O(k^2 c)$；更麻烦的是「归组」本身要处理传递性（A 与 B 同、B 与 C 同 ⇒ 三者一组），实现上还得配一个并查集或访问标记，既慢又绕。

瓶颈在于用「比较」来发现相等。而「相等」这件事有更好的表达方式：把内容本身当作键，扔进哈希表。相同内容自动落到同一个桶里，分组一步到位，既不需要两两比较，也不需要处理传递性——哈希表的键天然满足等价类划分。

于是整个算法定型为两个阶段。解析并分组：逐条扫描 paths，按空格切分，第一段是目录，其余每一段解析出文件名与内容，把 目录 + "/" + 文件名 追加到以内容为键的列表里。筛选并输出：遍历哈希表的所有值，只保留长度大于 1 的列表。

解析单个文件段是唯一需要小心的地方。段的形态是 文件名(内容)，其中文件名不含括号、内容不含右括号，所以可以用第一个 ( 的下标 idx 把它一刀两断：[0, idx) 是文件名，(idx, 长度-1) 是内容——右端取 长度 - 1 正是为了剥掉结尾的 )。这两个下标必须成对推导，任何一个偏一位都会把括号或最后一个字符混进结果。

不变量：扫描进行到任意时刻，哈希表里每个键是一份文件内容，对应的列表恰好是「到目前为止已扫描过的、内容等于该键的全部文件的完整路径」。因为每个文件只被解析一次、只被追加一次，列表里不会出现重复路径，也不会遗漏。

最后一步的筛选条件是 size() > 1：组内只有一个文件说明这份内容独一无二，不构成重复。这一步不能省，否则输出会混入大量单元素组。

输出顺序题目不作要求，所以直接遍历哈希表的值即可，不需要额外排序。

解题步骤

建一个 Map<String, List<String>> contentMap，键是文件内容、值是完整路径列表。为什么：题目判定重复的唯一依据是内容，把它当键就让「相同内容自动同组」成为哈希表的天然性质，省掉了两两比较和传递性合并；值用列表而不是计数，是因为最终要输出路径本身。

遍历 paths 的每一条记录，按空格切分成 parts。为什么：输入格式规定目录与各文件之间以空格分隔，且题目保证文件名与内容都不含空格，所以空格是安全的分隔符。

取 parts[0] 作为目录 dir。为什么：格式规定第一段固定是目录路径，后面才是文件；把它单独拎出来，内层循环就可以从下标 1 开始。

内层从下标 1 开始遍历剩余各段。为什么：跳过已被取走的目录段；若某条记录只有目录（parts.length == 1），循环一次都不进，边界自然成立，不需要特判。

对每段先定位第一个 ( 的下标 idx。为什么：文件名中不含括号，所以第一个 ( 就是文件名与内容的分界；用「查找」而不是「假设固定长度」，才能适配任意长度的文件名。

文件名取 [0, idx)，内容取 (idx, len - 1)。为什么：文件名是括号之前的全部字符；内容从 idx + 1 开始（跳过左括号），到 len - 1 结束（substring 右端开区间，正好剥掉结尾的 )）。两个端点必须一起推导，少减一个 1 就会把 ) 混进内容，导致所有内容都带上多余字符——虽然此时分组结果碰巧仍然正确，但键的语义已经错了。

拼出 fullPath = dir + "/" + fileName，追加到 contentMap[content] 对应的列表。为什么：题目要求输出完整路径；用 computeIfAbsent（Go 里直接 append 到零值切片）可以在键首次出现时自动建列表，避免「先查后建」的两段式写法。

遍历哈希表的值，把 size() > 1 的列表加进结果。为什么：组内只有一个路径说明该内容不重复，按题意不能输出；条件是严格大于 1，写成 >= 1 会把所有文件都输出。

返回结果列表。为什么：题目不要求任何顺序，直接返回哈希表遍历产生的顺序即可。

以 paths = ["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)", "root 4.txt(efgh)"] 走一遍。

第一条记录切分得 ["root/a", "1.txt(abcd)", "2.txt(efgh)"]，dir = "root/a"。

处理 "1.txt(abcd)"：第一个 ( 在下标 5，文件名取 [0, 5) 得 "1.txt"，内容取 [6, 10)——总长 11，右端 11 - 1 = 10——得 "abcd"。完整路径 "root/a/1.txt"，追加到键 "abcd" 下，此时 contentMap["abcd"] = ["root/a/1.txt"]。

处理 "2.txt(efgh)"：同理得内容 "efgh"、路径 "root/a/2.txt"，contentMap["efgh"] = ["root/a/2.txt"]。

第二条记录 dir = "root/c"，解析出内容 "abcd"、路径 "root/c/3.txt"。键 "abcd" 已存在，直接追加，变成 ["root/a/1.txt", "root/c/3.txt"]——两个来自不同目录、文件名也不同的文件，仅因内容相同就自动落进了同一个桶，这就是用内容当键的全部价值。

第三条记录 dir = "root"，解析出内容 "efgh"、路径 "root/4.txt"，键 "efgh" 的列表变成 ["root/a/2.txt", "root/4.txt"]。

扫描结束，哈希表有两个键，两个列表长度都是 2，都大于 1，全部进入结果：[["root/a/1.txt", "root/c/3.txt"], ["root/a/2.txt", "root/4.txt"]]。

若把第二条记录去掉，键 "abcd" 的列表只剩一个元素，size() > 1 不成立而被过滤掉，输出只剩一组——这正是「单个文件不算重复」那条规则的体现。

代码实现

class Solution {
    public List<List<String>> findDuplicate(String[] paths) {
        // 以内容为键：相同内容自动落入同一桶，无需两两比较。
        Map<String, List<String>> contentMap = new HashMap<>();

        for (String path : paths) {
            String[] parts = path.split(" ");
            String dir = parts[0];
            // 从 1 开始跳过目录段；只有目录时循环不进，边界自然成立。
            for (int i = 1; i < parts.length; i++) {
                // 文件名不含括号，第一个 '(' 即分界点。
                int idx = parts[i].indexOf('(');
                String fileName = parts[i].substring(0, idx);
                // 右端取 length - 1，正好剥掉结尾的 ')'。
                String content = parts[i].substring(idx + 1, parts[i].length() - 1);
                String fullPath = dir + "/" + fileName;
                contentMap.computeIfAbsent(content, key -> new ArrayList<>()).add(fullPath);
            }
        }

        List<List<String>> res = new ArrayList<>();
        for (List<String> group : contentMap.values()) {
            // 只有一个路径说明内容不重复，按题意不输出。
            if (group.size() > 1) {
                res.add(group);
            }
        }
        return res;
    }
}

func findDuplicate(paths []string) [][]string {
    // 以内容为键：相同内容自动落入同一桶，无需两两比较。
    contentMap := make(map[string][]string)

    for _, path := range paths {
        parts := strings.Split(path, " ")
        dir := parts[0]

        // 跳过目录段；只有目录时切片为空，循环不进。
        for _, file := range parts[1:] {
            // 文件名不含括号，第一个 '(' 即分界点。
            idx := strings.Index(file, "(")
            fileName := file[:idx]
            // 右端取 len(file)-1，正好剥掉结尾的 ')'。
            content := file[idx+1 : len(file)-1]

            fullPath := dir + "/" + fileName
            contentMap[content] = append(contentMap[content], fullPath)
        }
    }

    res := [][]string{}
    for _, group := range contentMap {
        // 只有一个路径说明内容不重复，按题意不输出。
        if len(group) > 1 {
            res = append(res, group)
        }
    }

    return res
}

复杂度分析

时间复杂度：$O(L)$，L 为所有输入字符串的总字符数。凭什么：每条记录被切分一次、每个文件段被解析一次，切分与截取的代价都与字符数成正比；哈希表的插入需要对内容串求一次哈希（同样是 $O(内容长度)$）并在冲突时做一次比较，所有文件的内容长度之和不超过 L；最后一趟遍历哈希表只与分组数有关，不超过文件数。相比两两比较的 $O(k^2 c)$，这里彻底消掉了平方项。

空间复杂度：$O(L)$。凭什么：哈希表的键是全部不同的内容串，值是全部完整路径，两者之和与输入总量同阶；切分产生的中间数组同样是 $O(单条记录长度)$，逐条释放。结果列表复用了值列表的引用（Java 中直接 add 同一个 List），没有额外拷贝。

关键点总结

「按某个属性把元素归类」的需求，第一反应就该是用该属性做哈希表的键，而不是两两比较。哈希表的键天然完成等价类划分，连传递性都不用自己处理——这是「分组类」问题的通用起手式，49 题字母异位词分组是同一个模子。

键的选择直接体现对题意的理解。本题判重依据是内容而非文件名或路径，所以键必须是内容；如果误把文件名当键，题目就被做成了另一道题。动手前先问一句「什么相同算重复」。

值存什么取决于输出要什么。这里要输出路径，所以值是路径列表；如果只问「有多少组重复」，值可以退化成计数器，空间会小很多。

字符串解析要用锚点定位而非固定长度假设。第一个 ( 和结尾的 ) 就是本题的两个锚点，substring(idx + 1, len - 1) 的两个端点必须一起推导，任何一处偏移都会污染键。

筛选条件写 > 1 而不是 >= 1，是「重复」这个词的直接翻译。这类差一错误在测试样例较小时很难暴露，读题时就要把它标出来。

面试延伸：题目自带的追问值得主动展开——真实系统中文件内容可能是 GB 级，不适合整份当键。工程做法是分层过滤：先按文件大小分桶（大小不同必不相同），再对同桶文件取内容哈希（如 MD5 / SHA-1）二次分桶，最后只对哈希相同的少数候选做逐字节比对，以规避哈希碰撞。若还要考虑 IO，可以先只读文件头尾各若干字节做快速排除。

易错点总结

用文件名当哈希表的键：["root/a 1.txt(aaa)", "root/b 1.txt(bbb)"] → 两个同名但内容不同的文件被归为一组，返回一组重复，正确答案是空列表。

内容截取时右端写成 parts[i].length()："1.txt(abcd)" → 内容变成 "abcd)"，虽然分组结果碰巧仍正确（所有键都多一个 )），但键的语义已错；一旦后续要用内容做别的判断就会全线出问题。

用 lastIndexOf('(') 定位分界：文件名保证不含括号，但若内容中出现 ( → 分界点跑到内容内部，文件名和内容都被切错。应当用第一个 (。

假设文件名长度固定、用魔法数字截取："12345.txt(x)" → 文件名长度不同的输入立刻错位，解析出乱七八糟的键。

内层循环从下标 0 开始：parts[0] 是目录不含括号 → indexOf('(') 返回 -1，substring(0, -1) 直接抛异常。

筛选条件写成 size() >= 1：所有文件内容互不相同 → 每个单元素组都被输出，正确答案是空列表。

拼接路径时漏掉 /：dir = "root/a"、fileName = "1.txt" → 得到 "root/a1.txt"，路径格式错误。

拼接路径时把内容也带上："root/a/1.txt(abcd)" → 输出格式与期望不符，判题失败。

两两比较所有文件的内容来分组：文件数上万时 → $O(k^2)$ 次比较直接超时，而且还要额外处理「A 与 B 同、B 与 C 同」的合并。

用 path.split(" ") 却没意识到目录必须单独取：把 parts 整体当作文件列表 → 目录被当成文件解析，同上抛异常或产生垃圾键。

相似题目

题目	难度	考察点
49. 字母异位词分组	中等	同为「按属性分组」，但键需要先归一化（排序或计数）才能让异位词落进同桶
652. 寻找重复的子树	中等	键是子树的序列化结果，考的是如何把树结构压成可比较的字符串
187. 重复的DNA序列	中等	键是定长滑动窗口的子串，可用滚动哈希把每次取键降到 $O(1)$
217. 存在重复元素	简单	只判断有无重复而不必分组，用哈希集合即可，是本题的最简形态
219. 存在重复元素 II	简单	重复还要满足下标距离限制，哈希表的值从列表退化成「最近一次出现的下标」
242. 有效的字母异位词	简单	只比较两个串是否同组，用计数数组直接对比，不需要建表
451. 根据字符出现频率排序	中等	先用哈希表统计再按值排序，重点在「统计完之后怎么用」而非分组本身
290. 单词规律	简单	需要双向映射保证一一对应，单向哈希表会漏掉「两个模式字符映射到同一词」