面试 Two Pointers HashMap Stack 模式

编码面试算法三大必备模式

双指针模式使用两个指针单次遍历数据，将复杂度从 O(n²) 降到 O(n)，特别适合回文串、元素配对和过滤任务。

主要两种变体：

• 左右收敛：左指针从索引 0 开始，右指针从字符串末尾开始，向中间移动，用于对称性检查。
• 慢快指针：慢指针更新结果，快指针提前扫描，用于去重或元素移位。

示例：忽略非字母字符检查回文串。

const isPalindrome = (s) => {
  let left = 0;
  let right = s.length - 1;

  while (left < right) {
    if (s[left] !== s[right]) {
      return false;
    }
    left++;
    right--;
  }

  return true;
};

console.log(isPalindrome("madam")); // true
console.log(isPalindrome("abc")); // false

HashMap：快速查找与分组

HashMap（对象或 Map）存储键值对，实现 O(1) 访问时间。完美适用于频率统计、唯一性检查、异位词和缓存场景。

算法：第一遍构建，第二遍查询，完全避免嵌套循环。

示例：字符串中第一个不重复字符。

const firstUniqueChar = (s) => {
  const map = {};

  for (const char of s) {
    map[char] = (map[char] || 0) + 1;
  }

  for (const char of s) {
    if (map[char] === 1) {
      return char;
    }
  }

  return null;
};

console.log(firstUniqueChar("banana")); // 'b'
console.log(firstUniqueChar("aabbc")); // 'c'

栈：处理后进先出结构

栈遵循后进先出原则。数组通过 push/pop 操作，在括号验证、无递归栈和回溯问题中大放异彩。

示例：验证括号序列有效性。

const isValidBrackets = (s) => {
  const stack = [];
  const map = {
    ')': '(', 
    ']': '[',
    '}': '{' 
  };

  for (const char of s) {
    if ('([{'.includes(char)) {
      stack.push(char);
    } else {
      const last = stack.pop();
      if (last !== map[char]) {
        return false;
      }
    }
  }

  return stack.length === 0;
};

console.log(isValidBrackets("{[()()]}")); // true
console.log(isValidBrackets("{[(])}")); // false

何时使用这些模式

编码前，留意这些信号：

双指针：

• 数组/字符串有对称性（回文）。
• 寻找元素配对。
• 已排序数组。
• 从两端比较。

HashMap：

• 统计频率或唯一性。
• 异位词、分组。
• 检查元素是否存在。
• 无序数据需要快速查找。

栈：

• 括号或嵌套结构。
• 后进先出逻辑（最后打开的先关闭）。
• 回溯或状态历史。

核心要点

• 双指针减少遍历次数，完美适配线性结构。
• HashMap 提供 O(1) 访问，用两次遍历替换嵌套循环。
• 栈确保嵌套顺序正确，无需递归。
• 练习建议：每个模式刷 10 题，然后混合使用。

这些模式能搞定大部分 LeetCode/Codewars 简单/中等题。持续练习，就能培养高级面试直觉。

— Editorial Team