题库/手写题/题目详解
手写题答案约 5 分钟阅读

基础算法：Map、双指针、栈、二分

先理解原理和示例，再练习完整口述与追问。

回答要点

输入前提、复杂度、重复值、空结果；DFS/BFS 已在第 4 题给出。

原理拆解

算法先说不变量：Map 两数之和保存此前见过的值；双指针依赖有序或可推进的区间；栈保存待匹配状态；二分每轮排除确定不含目标的一半。时间复杂度由输入规模与循环推进决定，不能看见两个循环就一律 O(n²)。

示例与推演

两数之和 [2,7,11] 目标 9：读 2 时查 7 未命中并登记 2，读 7 时查 2 命中；二分明确区间是闭区间还是半开区间，再统一 left/right 更新。测试空输入、边界目标、重复值与找不到。

易错点

不要在不满足单调性或有序条件的数据上二分。索引复用、溢出、空栈和无限循环都是面试重点。

参考回答可直接练习口述

哈希表适合边遍历边查补数；有序数组可以用双指针；括号匹配用栈；二分依赖有序性并要统一边界。先确认题目是找一个结果还是所有结果、返回下标还是值，以及重复数据规则，再写代码。

js
function twoSum(values, target) {
  const seen = new Map()
  for (let i = 0; i < values.length; i++) {
    const complement = target - values[i]
    if (seen.has(complement)) return [seen.get(complement), i]
    seen.set(values[i], i)
  }
  return null
}

function twoSumSorted(values, target) {
  let left = 0
  let right = values.length - 1
  while (left < right) {
    const sum = values[left] + values[right]
    if (sum === target) return [left, right]
    if (sum < target) left++
    else right--
  }
  return null
}

function validBrackets(text) {
  const pairs = new Map([[')', '('], [']', '['], ['}', '{']])
  const stack = []
  for (const char of text) {
    if (char === '(' || char === '[' || char === '{') stack.push(char)
    else if (!pairs.has(char) || stack.pop() !== pairs.get(char)) return false
  }
  return stack.length === 0
}

function binarySearch(values, target) {
  let left = 0
  let right = values.length - 1
  while (left <= right) {
    const middle = left + Math.floor((right - left) / 2)
    if (values[middle] === target) return middle
    if (values[middle] < target) left = middle + 1
    else right = middle - 1
  }
  return -1
}

示例与复杂度：twoSum([3,3],6) 为 [0,1]，平均 O(n) 时间/O(n) 空间；有序双指针 O(n)/O(1)；validBrackets('([{}])') 为 true，'([)]' 为 false，O(n)/O(n)，本题只接受括号字符；二分 O(log n)/O(1)，有重复值时返回某个匹配下标，不保证第一个。数值例子按有限、可安全运算的数值处理，不解决任意大数和金额舍入。