集合算法题解题思路与代码分析

1. 哈希集合基础应用（Set）

核心解题思路

哈希集合（Set）的核心特性是元素唯一性和快速查找（O(1)）。常用于：

• 判断元素是否存在（去重）
• 记录访问过的状态（如环检测、快乐数）
• 求交集、并集

经典例题：217. 存在重复元素

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    const set = new Set();
    for (let num of nums) {
        // 如果 Set 中已经存在当前元素，说明有重复
        if (set.has(num)) {
            return true;
        }
        set.add(num);
    }
    return false;
};

关键点：

• 利用 Set 的 has 和 add 方法，一次遍历即可判断。
• 时间复杂度 O(n)，空间复杂度 O(n)。

经典例题：349. 两个数组的交集

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
    const set1 = new Set(nums1);
    const set2 = new Set(nums2);
    // 遍历较小的 Set，判断元素是否在另一个 Set 中
    const result = [];
    for (let num of set1) {
        if (set2.has(num)) {
            result.push(num);
        }
    }
    return result;
};

关键点：

• 将两个数组转为 Set 去重，然后遍历较小 Set 检查交集。
• 时间复杂度 O(m + n)，空间复杂度 O(m + n)。

2. 哈希映射进阶应用（Map）

核心解题思路

哈希映射（Map）存储键值对，常用于：

• 统计频率（字符出现次数）
• 记录元素与索引的对应关系
• 缓存计算结果
• 实现 LRU 等复杂数据结构

经典例题：1. 两数之和

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        // 如果存在 complement，说明找到了两个数
        if (map.has(complement)) {
            return [map.get(complement), i];
        }
        // 将当前元素及其下标存入 Map
        map.set(nums[i], i);
    }
    return [];
};

关键点：

• 一边遍历一边构建 Map，存储已经遍历过的元素及其下标。
• 对于当前元素 nums[i]，检查 target - nums[i] 是否在 Map 中，如果在则找到答案。
• 时间复杂度 O(n)，空间复杂度 O(n)。

经典例题：49. 字母异位词分组

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    const map = new Map();
    for (let str of strs) {
        // 将字符串排序后作为键
        const sorted = str.split('').sort().join('');
        if (!map.has(sorted)) {
            map.set(sorted, []);
        }
        map.get(sorted).push(str);
    }
    // 返回 Map 的所有值组成的数组
    return Array.from(map.values());
};

关键点：

• 字母异位词排序后得到相同字符串，可作为 Map 的键。
• 将原字符串放入对应键的数组中，完成分组。
• 时间复杂度 O(n * k log k)，其中 k 为字符串最大长度。

3. 并查集（Union-Find）

核心解题思路

并查集用于处理不相交集合的合并与查询问题。核心操作：

• find(x)：查找元素 x 所属集合的根节点（通常带路径压缩）
• union(x, y)：合并 x 和 y 所在的集合
• 连通分量计数：初始化时每个元素自成一派，每合并一次减少一个集合

经典例题：547. 省份数量

/**
 * @param {number[][]} isConnected
 * @return {number}
 */
var findCircleNum = function(isConnected) {
    const n = isConnected.length;
    // 初始化并查集，每个城市的父节点指向自己
    const parent = new Array(n).fill(0).map((_, i) => i);
    // 路径压缩的 find 函数
    function find(x) {
        if (parent[x] !== x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }
    // 合并函数
    function union(x, y) {
        const rootX = find(x);
        const rootY = find(y);
        if (rootX !== rootY) {
            parent[rootY] = rootX; // 将 rootY 的根指向 rootX
        }
    }

    // 遍历矩阵，将相连的城市合并
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (isConnected[i][j] === 1) {
                union(i, j);
            }
        }
    }

    // 统计根节点的个数（即省份数量）
    let count = 0;
    for (let i = 0; i < n; i++) {
        if (find(i) === i) count++;
    }
    return count;
};

关键点：

• 并查集初始化：每个节点的父节点是自己。
• find 函数实现路径压缩，使后续查找更快。
• 遍历矩阵，对相连的城市执行 union 操作。
• 最后统计有多少个节点的父节点是自身（即根节点），即为省份数量。

经典例题：684. 冗余连接

/**
 * @param {number[][]} edges
 * @return {number[]}
 */
var findRedundantConnection = function(edges) {
    const n = edges.length;
    const parent = new Array(n + 1).fill(0).map((_, i) => i); // 节点编号从1开始

    function find(x) {
        if (parent[x] !== x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    function union(x, y) {
        const rootX = find(x);
        const rootY = find(y);
        if (rootX === rootY) {
            return false; // 已经连通，说明当前边是冗余的
        }
        parent[rootY] = rootX;
        return true;
    }

    for (let [u, v] of edges) {
        if (!union(u, v)) {
            return [u, v]; // 返回第一条导致环的边
        }
    }
    return [];
};

关键点：

• 遍历每条边，尝试合并两个节点。
• 如果两个节点已经在同一集合中（即 find 结果相同），则当前边是冗余的，直接返回。
• 因为题目保证只有一个冗余连接，所以找到后即可返回。

4. 集合与其他算法的结合

核心解题思路

集合（Set/Map）常作为辅助工具，与回溯、DFS、BFS、滑动窗口等算法结合，用于去重、记录状态、快速查找等。

经典例题：36. 有效的数独

/**
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function(board) {
    // 用三个二维数组分别记录行、列、九宫格中出现的数字
    const rows = new Array(9).fill(0).map(() => new Set());
    const cols = new Array(9).fill(0).map(() => new Set());
    const boxes = new Array(9).fill(0).map(() => new Set());

    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            const num = board[i][j];
            if (num === '.') continue;

            // 计算九宫格索引
            const boxIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3);

            // 检查当前数字是否已经在对应行、列、九宫格中出现过
            if (rows[i].has(num) || cols[j].has(num) || boxes[boxIndex].has(num)) {
                return false;
            }

            rows[i].add(num);
            cols[j].add(num);
            boxes[boxIndex].add(num);
        }
    }
    return true;
};

关键点：

• 使用三个 Set 数组分别记录每行、每列、每个九宫格中已出现的数字。
• 遍历每个格子，对于数字字符，检查其是否已在对应的行、列、九宫格中出现，若出现则无效。
• 九宫格索引公式：boxIndex = Math.floor(i/3)*3 + Math.floor(j/3)。

经典例题：90. 子集 II（回溯 + 去重）

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function(nums) {
    nums.sort((a, b) => a - b); // 排序，方便去重
    const result = [];
    const path = [];

    function backtrack(start) {
        result.push([...path]); // 记录当前路径（子集）
        for (let i = start; i < nums.length; i++) {
            // 同层去重：如果当前元素和前一个元素相同，则跳过
            if (i > start && nums[i] === nums[i - 1]) continue;
            path.push(nums[i]);
            backtrack(i + 1);
            path.pop();
        }
    }

    backtrack(0);
    return result;
};

关键点：

• 排序是去重的前提。
• 在递归的同一层（即 start 相同的循环中），如果当前元素与前一个元素相同，说明会产生重复子集，直接跳过。
• 这里虽然没有直接使用 Set，但利用排序和判断实现了去重，是集合思想的体现。如果一定要用 Set，可以将子集转为字符串存入 Set，但效率较低。

总结

集合相关题目在面试中非常高频，熟练掌握 Set、Map 以及并查集的操作，能帮助你解决一大类问题。建议练习顺序：

1. Set/Map 基础：217. 存在重复元素、1. 两数之和
2. Map 进阶：49. 字母异位词分组、560. 和为 K 的子数组
3. 并查集入门：547. 省份数量、684. 冗余连接
4. 综合应用：36. 有效的数独、90. 子集 II