代码随想录 — 哈希与字符串

对应 leetcode-master：哈希表理论基础、242/349/202/1/454/383、15/18、344/541/KMP/151/459 等。

---

一、哈希表理论基础（何时用、怎么选结构）

• 作用：根据关键码直接访问，快速判断一个元素是否在集合里（O(1) 查询），典型用法是「有没有出现过」「出现几次」。
• 实现：哈希函数把 key 映射到下标；哈希碰撞用拉链法（冲突的放链表）或线性探测（往后找空位）。一般用语言内置的哈希表即可。
• 常见三种结构：
  • 数组：key 是连续整数或小范围（如 26 个字母）时，用数组当哈希表，下标即 key。
  • Set：只关心「有没有」，不关心次数或下标时用 Set（如去重、是否存在）。
  • Map：需要 key → value（如「值 → 下标」「值 → 次数」）时用 Map。

何时想到哈希：题目里出现「判断是否出现过」「找配对」「统计次数」等，优先考虑哈希，用空间换时间。

---

二、两数之和（1）— 为什么用 Map

题意：在数组中找两个数之和为 target，返回两数的下标。

为什么不用 Set：不仅要判断「target - 当前数」是否存在，还要知道它的下标，所以需要 key = 数值，value = 下标，用 Map。

思路：遍历数组，对当前数 nums[i]，在 Map 里查是否存在 target - nums[i]；若有则返回 [map.get(target - nums[i]), i]；若无则把 (nums[i], i) 放入 Map（表示「值为 nums[i] 的下标是 i」）。这样每个数只遍历一次，且用到的是「之前已经遍历过的数」的下标。

易错：Map 里存的是「已经遍历过的数 → 其下标」，查的是「与当前数配对的数」是否出现过，别把 key/value 搞反。

---

三、哈希表其它经典题（思路一句话）

• 242 有效的字母异位词：两串长度相同且各字符出现次数相同。用长度 26 的数组当哈希表，统计第一串各字母次数，再减第二串，若全 0 则是异位词。
• 349 两个数组的交集：去重 + 判断存在。用 Set 存一个数组，遍历另一个，在 Set 中的加入结果并可从 Set 删掉避免重复。
• 202 快乐数：按规则不断求平方和，若出现 1 则快乐；若出现重复则进入环，不快乐。用 Set 记录出现过的数，重复即 false。
• 454 四数相加 II：四个数组各取一个数求和为 0。可把前两数组的两两之和存 Map（和 → 出现次数），再枚举后两数组的两两之和，查 Map 中是否有相反数，累加次数。
• 383 赎金信：判断 magazine 的字符能否组成 ransomNote。用数组或 Map 统计 magazine 各字符数量，再减 ransomNote 的消耗，若有字符不够则 false。
• 15 三数之和：找所有和为 0 的三元组且不重复。排序 + 双指针更合适；固定一个数，在右侧用左右指针找两数之和为负的固定数。注意去重（固定数、左、右都要跳过重复）。
• 18 四数之和：同思路，固定两个数再双指针；同样注意去重和剪枝。

小结：需要「值 → 下标」用 Map；只 need「有没有」且 key 范围小用数组，否则用 Set；若还要去重或有序，再考虑 set/map 的有序版本。

---

四、字符串 — 反转与空格（344 / 541 / 151）

• 344 反转字符串：原地反转，左右指针交换即可。
• 541 反转字符串 II：每 2k 个字符为一组，每组内只反转前 k 个。按题意模拟，注意最后一组可能不足 2k。
• 151 翻转字符串里的单词：先整体反转，再对每个单词内部反转；或先按空格 split 再 reverse 再 join。若要求 O(1) 空间，需在原串上先去掉多余空格再按「整体反转 + 逐词反转」做。

---

五、KMP 与 重复子串（28 实现 strStr / 459）

KMP 核心：当模式串与主串在某位失配时，不回溯主串指针，而是根据已匹配部分利用 next 数组（最长相等前后缀长度）把模式串指针回退到合适位置，继续比较。

• next 数组：next[i] 表示模式串 [0, i-1] 这段子串的「最长相等真前后缀」长度。求 next 的过程本身也是一个「模式串与自身」的匹配，用双指针或递推实现。
• 28 实现 strStr：主串中找模式串首次出现位置，用 KMP 或暴力均可；KMP 时间 O(n+m)。

459 重复的子字符串：判断 s 是否由某子串重复多次构成。思路一：s + s 拼起来，去掉首尾各一个字符后，若还能找到 s，则是重复子串。思路二：用 KMP 的 next 数组，若 len % (len - next[len-1]) === 0 且 next[len-1] !== 0，则说明有重复周期。

 // KMP实现 strStr
   function strStr(haystack, needle) {
     if (needle === "") return 0;
     const n = needle.length;
     const lps = Array(n).fill(0);

     // build LPS
     for (let i = 1, len = 0; i < n; ) {
       if (needle[i] === needle[len]) {
         lps[i++] = ++len;
       } else if (len > 0) {
         len = lps[len - 1];
       } else {
         lps[i++] = 0;
       }
     }

     // search
     for (let i = 0, j = 0; i < haystack.length; ) {
       if (haystack[i] === needle[j]) {
         i++; j++;
         if (j === n) return i - j;
       } else if (j > 0) {
         j = lps[j - 1];
       } else {
         i++;
       }
     }
     return -1;
   }

---

六、字符串总结

类型	方法
反转	双指针交换；或 split/reverse/join（非 O(1) 空间）
匹配 / 子串	KMP（next 数组、失配回退）；重复子串可结合 next 的周期性质
哈希	统计字符用数组（26/128）；需要 key-value 用 Map

建议：两数之和的「为什么用 Map、key/value 存什么」要能说清；KMP 至少理解「next 是什么、怎么用」，能写出求 next 和匹配主流程即可。

---

附：核心代码模板

两数之和（Map）

// JavaScript — 时间 O(n)，空间 O(n)
function twoSum(nums, target) {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (map.has(complement)) return [map.get(complement), i];
    map.set(nums[i], i);
  }
  return [];
}

有效的字母异位词（数组哈希）

// JavaScript — 时间 O(n)，空间 O(1)
function isAnagram(s, t) {
  if (s.length !== t.length) return false;
  const count = new Array(26).fill(0);
  for (let i = 0; i < s.length; i++) {
    count[s.charCodeAt(i) - 97]++;
    count[t.charCodeAt(i) - 97]--;
  }
  return count.every(c => c === 0);
}

KMP — 求 next 数组 + 匹配

// JavaScript — 时间 O(n+m)
function strStr(haystack, needle) {
  if (!needle.length) return 0;
  // 构建 next 数组（最长相等前后缀长度）
  const next = [0];
  let j = 0;
  for (let i = 1; i < needle.length; i++) {
    while (j > 0 && needle[i] !== needle[j]) j = next[j - 1];
    if (needle[i] === needle[j]) j++;
    next.push(j);
  }
  // 匹配
  j = 0;
  for (let i = 0; i < haystack.length; i++) {
    while (j > 0 && haystack[i] !== needle[j]) j = next[j - 1];
    if (haystack[i] === needle[j]) j++;
    if (j === needle.length) return i - needle.length + 1;
  }
  return -1;
}

# Python — KMP
def str_str(haystack: str, needle: str) -> int:
    if not needle:
        return 0
    # 构建 next
    nxt = [0] * len(needle)
    j = 0
    for i in range(1, len(needle)):
        while j > 0 and needle[i] != needle[j]:
            j = nxt[j - 1]
        if needle[i] == needle[j]:
            j += 1
        nxt[i] = j
    # 匹配
    j = 0
    for i in range(len(haystack)):
        while j > 0 and haystack[i] != needle[j]:
            j = nxt[j - 1]
        if haystack[i] == needle[j]:
            j += 1
        if j == len(needle):
            return i - len(needle) + 1
    return -1