数据结构与常用算法模板

🧮 算法面试的核心是模式识别。掌握常用模板，在题目中快速匹配模式，比死记硬背解法更高效。

时间复杂度速查

复杂度	名称	示例
O(1)	常数	哈希查找
O(log n)	对数	二分查找
O(n)	线性	线性扫描
O(n log n)	线性对数	归并排序
O(n²)	平方	冒泡排序
O(2ⁿ)	指数	回溯全子集

---

常用模板

双指针

// 对撞指针：有序数组两数之和
function twoSum(nums: number[], target: number): number[] {
  let left = 0, right = nums.length - 1
  while (left < right) {
    const sum = nums[left] + nums[right]
    if (sum === target) return [left, right]
    else if (sum < target) left++
    else right--
  }
  return []
}

// 快慢指针：链表判环
function hasCycle(head: ListNode | null): boolean {
  let slow = head, fast = head
  while (fast && fast.next) {
    slow = slow!.next
    fast = fast.next.next
    if (slow === fast) return true
  }
  return false
}

滑动窗口

// 最长无重复子串
function lengthOfLongestSubstring(s: string): number {
  const map = new Map<string, number>()
  let left = 0, maxLen = 0
  for (let right = 0; right < s.length; right++) {
    if (map.has(s[right])) {
      left = Math.max(left, map.get(s[right])! + 1)
    }
    map.set(s[right], right)
    maxLen = Math.max(maxLen, right - left + 1)
  }
  return maxLen
}

二分查找

// 标准模板（找第一个 >= target 的位置）
function lowerBound(nums: number[], target: number): number {
  let left = 0, right = nums.length
  while (left < right) {
    const mid = (left + right) >> 1
    if (nums[mid] < target) left = mid + 1
    else right = mid
  }
  return left
}

BFS / 最短路

function bfs(graph: number[][], start: number): number[] {
  const dist = new Array(graph.length).fill(Infinity)
  dist[start] = 0
  const queue: number[] = [start]
  while (queue.length) {
    const node = queue.shift()!
    for (const neighbor of graph[node]) {
      if (dist[neighbor] === Infinity) {
        dist[neighbor] = dist[node] + 1
        queue.push(neighbor)
      }
    }
  }
  return dist
}

动态规划

// 0-1 背包
function knapsack(weights: number[], values: number[], W: number): number {
  const dp = new Array(W + 1).fill(0)
  for (let i = 0; i < weights.length; i++) {
    for (let w = W; w >= weights[i]; w--) {  // 逆序防重用
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i])
    }
  }
  return dp[W]
}

回溯

// 全排列模板
function permute(nums: number[]): number[][] {
  const result: number[][] = []
  const used = new Array(nums.length).fill(false)
  function backtrack(path: number[]) {
    if (path.length === nums.length) { result.push([...path]); return }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue
      used[i] = true
      path.push(nums[i])
      backtrack(path)
      path.pop()
      used[i] = false
    }
  }
  backtrack([])
  return result
}

---

常见误区

• 二分查找边界条件写错（left < right vs left <= right），建议固定一个模板
• DFS 没有标记 visited，导致死循环
• 动态规划状态转移方向错误（背包应逆序遍历）