字典算法题解题思路与代码分析

一、哈希表基础应用

经典例题：1. 两数之和

题目：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

解题思路：利用哈希表存储已经遍历过的元素及其下标。遍历数组，对于当前元素 nums[i]，计算 complement = target - nums[i]，检查 complement 是否在哈希表中。如果在，则找到答案；如果不在，将 nums[i] 及其下标存入哈希表。

/**
 * @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 已经在 map 中，说明找到了两个数
        if (map.has(complement)) {
            return [map.get(complement), i];
        }
        // 否则将当前元素加入 map
        map.set(nums[i], i);
    }
    return []; // 题目保证有解，不会执行到这里
};

关键点：

• 利用哈希表 O(1) 查找特性，将暴力解 O(n²) 优化到 O(n)。
• 注意是先查找再插入，避免同一个元素被使用两次（如 target=6，nums=[3,3] 时仍可正确处理）。

经典例题：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());
};

关键点：

• 排序的时间复杂度 O(k log k)，其中 k 为字符串最大长度。
• 利用哈希表分组，键是排序后的字符串，值是原字符串数组。
• 若不想排序，也可用字符计数数组作为键（如将 'aabb' 编码为 a2b2），但实现稍复杂。

经典例题：560. 和为 K 的子数组

题目：给你一个整数数组 nums 和一个整数 k，请你统计并返回该数组中和为 k 的连续子数组的个数。

解题思路：使用前缀和 + 哈希表。定义 prefixSum[i] 表示 nums[0] 到 nums[i-1] 的和。子数组 nums[j..i] 的和为 prefixSum[i+1] - prefixSum[j]。要找到和为 k 的子数组，即需要找到满足 prefixSum[i] - prefixSum[j] = k 的 j，也就是 prefixSum[j] = prefixSum[i] - k。遍历时，用哈希表记录每个前缀和出现的次数，对于当前前缀和 currentSum，只需查询哈希表中 currentSum - k 的出现次数，累加到结果中。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function(nums, k) {
    const map = new Map();
    map.set(0, 1); // 前缀和为0出现1次（空数组）
    let count = 0;
    let prefixSum = 0;

    for (let num of nums) {
        prefixSum += num;
        // 如果存在前缀和为 prefixSum - k，说明这些位置到当前位置的子数组和为k
        if (map.has(prefixSum - k)) {
            count += map.get(prefixSum - k);
        }
        // 更新当前前缀和的出现次数
        map.set(prefixSum, (map.get(prefixSum) || 0) + 1);
    }
    return count;
};

关键点：

• 通过前缀和将子数组和问题转化为两数之差问题。
• 哈希表存储前缀和出现的次数，可以一次遍历完成统计。
• 注意初始化 map.set(0, 1)，表示前缀和为 0 出现 1 次，用于处理从数组开头到当前位置的子数组和恰好为 k 的情况。

二、字典树（Trie）

经典例题：208. 实现 Trie (前缀树)

题目：实现一个 Trie，包含 insert, search 和 startsWith 这三个操作。

解题思路：Trie 节点包含两个属性：children（对象或数组）和 isEnd（标记是否为单词结尾）。插入时从根节点逐层创建子节点；查找时逐层检查是否存在相应子节点，最后检查 isEnd；前缀查找与查找类似，但不需要检查 isEnd。

var Trie = function() {
    this.children = {}; // 存储子节点，键为字符，值为 Trie 节点
    this.isEnd = false; // 标记是否是单词结尾
};

/**
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {
    let node = this;
    for (let char of word) {
        if (!node.children[char]) {
            node.children[char] = new Trie();
        }
        node = node.children[char];
    }
    node.isEnd = true;
};

/**
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
    let node = this;
    for (let char of word) {
        if (!node.children[char]) return false;
        node = node.children[char];
    }
    return node.isEnd === true;
};

/**
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function(prefix) {
    let node = this;
    for (let char of prefix) {
        if (!node.children[char]) return false;
        node = node.children[char];
    }
    return true;
};

关键点：

• 每个节点用一个对象存储子节点，键为字符，值为子 Trie 节点。
• isEnd 标记表示从根到当前节点的路径构成了一个完整的单词。
• 插入和查找时间复杂度 O(len(word))，空间复杂度 O(所有字符总数)。

经典例题：211. 添加与搜索单词 - 数据结构设计

题目：设计一个数据结构，支持添加单词和搜索单词。搜索时，单词可能包含点号 '.'，它可以匹配任何一个字母。

解题思路：基于 Trie 树，插入单词与普通 Trie 相同。搜索时遇到点号 '.' 需要递归遍历所有子节点，使用 DFS（深度优先搜索）进行匹配。

var WordDictionary = function() {
    this.children = {};
    this.isEnd = false;
};

/**
 * @param {string} word
 * @return {void}
 */
WordDictionary.prototype.addWord = function(word) {
    let node = this;
    for (let char of word) {
        if (!node.children[char]) {
            node.children[char] = new WordDictionary();
        }
        node = node.children[char];
    }
    node.isEnd = true;
};

/**
 * @param {string} word
 * @return {boolean}
 */
WordDictionary.prototype.search = function(word) {
    // 辅助递归函数
    const dfs = (node, index) => {
        if (index === word.length) {
            return node.isEnd; // 到达单词末尾，检查是否构成完整单词
        }
        const char = word[index];
        if (char === '.') {
            // 点号：尝试所有子节点
            for (let key in node.children) {
                if (dfs(node.children[key], index + 1)) {
                    return true;
                }
            }
            return false;
        } else {
            // 普通字符：必须有对应子节点
            if (!node.children[char]) return false;
            return dfs(node.children[char], index + 1);
        }
    };
    return dfs(this, 0);
};

关键点：

• 遇到 '.' 时，需要遍历当前节点的所有子节点进行递归搜索，直到找到匹配的路径。
• 时间复杂度：正常字符 O(1)，点号 '.' 可能需要遍历整个分支，最坏 O(所有单词字符总数)，但平均较好。
• 注意递归边界：当 index 到达单词末尾时，返回当前节点的 isEnd 值。

三、综合应用（哈希表 + 其他数据结构）

经典例题：146. LRU 缓存

题目：设计一个 LRU（最近最少使用）缓存数据结构，支持 get 和 put 操作，要求 get 和 put 的时间复杂度为 O(1)。

解题思路：使用哈希表 + 双向链表。哈希表存储键对应的链表节点，双向链表维护节点的访问顺序（最近访问的节点放在头部，最久未使用的在尾部）。get 操作将节点移动到头部；put 操作若键已存在则更新值并移动到头部，若不存在则插入新节点到头部，如果容量超限则删除尾部节点。

// 定义双向链表节点
class ListNode {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.prev = null;
        this.next = null;
    }
}

/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
    this.capacity = capacity;
    this.map = new Map(); // key -> ListNode
    // 虚拟头尾节点，方便操作
    this.head = new ListNode(0, 0);
    this.tail = new ListNode(0, 0);
    this.head.next = this.tail;
    this.tail.prev = this.head;
};

/**
 * 将节点移动到头部（表示最近使用）
 * @param {ListNode} node
 */
LRUCache.prototype.moveToHead = function(node) {
    this.removeNode(node);
    this.addToHead(node);
};

/**
 * 删除节点
 */
LRUCache.prototype.removeNode = function(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
};

/**
 * 将节点添加到头部
 */
LRUCache.prototype.addToHead = function(node) {
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next.prev = node;
    this.head.next = node;
};

/**
 * 删除尾部节点（最久未使用）
 */
LRUCache.prototype.removeTail = function() {
    const tailNode = this.tail.prev;
    this.removeNode(tailNode);
    return tailNode;
};

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    if (!this.map.has(key)) return -1;
    const node = this.map.get(key);
    // 移动到头部表示最近使用
    this.moveToHead(node);
    return node.value;
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    if (this.map.has(key)) {
        // 键已存在，更新值并移动到头部
        const node = this.map.get(key);
        node.value = value;
        this.moveToHead(node);
    } else {
        // 键不存在，创建新节点
        const newNode = new ListNode(key, value);
        this.map.set(key, newNode);
        this.addToHead(newNode);
        // 如果超过容量，删除尾部节点
        if (this.map.size > this.capacity) {
            const tailNode = this.removeTail();
            this.map.delete(tailNode.key);
        }
    }
};

关键点：

• 哈希表提供 O(1) 的节点查找，双向链表提供 O(1) 的节点移动和删除。
• 使用虚拟头尾节点简化边界条件处理。
• moveToHead = removeNode + addToHead 两步完成。
• 删除尾部节点时需要同时从哈希表和链表中移除。

总结

• 哈希表 常用于快速查找、计数、去重，是算法题中最基础也最高频的数据结构。
• 字典树 专门用于处理字符串前缀问题，能高效地存储和查找字符串集合。
• 综合应用 往往需要哈希表与其他数据结构（链表、堆）结合，实现更复杂的功能。

建议按以下顺序练习：

1. 哈希表基础：1. 两数之和 → 242. 有效的字母异位词
2. 哈希表进阶：49. 字母异位词分组 → 560. 和为 K 的子数组
3. 字典树入门：208. 实现 Trie
4. 字典树进阶：211. 添加与搜索单词
5. 综合应用：146. LRU 缓存