刷了500道LeetCode，终于明白大厂算法面试到底考什么

算法面试不是考你背了多少题，而是考你能不能在面试官面前把问题拆解清楚、写出正确的代码。

先泼一盆冷水

有个候选人在面试前刷了600道LeetCode，信心满满。

面试时遇到一道Medium难度的题，他说："这题我做过！"然后飞快地写完代码。

面试官问："时间复杂度是多少？"

他卡住了。

面试官又问："如果数据量是10亿呢？"

他彻底懵了。

最后他挂在了一道刷过的题上。

问题出在哪？ 他只记住了答案，没有理解解题思路。

这篇文章不是让你背题，而是让你理解：

面试官出算法题的真实意图
不同数据结构解决什么问题
如何分析复杂度、选择合适的方案

一、面试官出算法题的真实目的

先搞清楚规则，才能赢得游戏。

考察点一：编码基本功

// 看这两段代码，哪个更专业？

// 版本A：能跑，但像刚学编程
func f(a []int, t int) int {
    for i := 0; i < len(a); i++ {
        for j := i + 1; j < len(a); j++ {
            if a[i] + a[j] == t {
                return i
            }
        }
    }
    return -1
}

// 版本B：清晰的变量命名、完整的逻辑
func twoSum(nums []int, target int) []int {
    seen := make(map[int]int) // 存储已遍历的数字及其索引

    for i, num := range nums {
        complement := target - num
        if idx, exists := seen[complement]; exists {
            return []int{idx, i}
        }
        seen[num] = i
    }

    return nil // 无解的情况
}

面试官能从代码中看出：

命名规范：变量名是否有意义
边界处理：空数组、无解怎么办
代码结构：逻辑是否清晰

考察点二：思考过程

比写出正确代码更重要的是：你是怎么想到这个解法的。

面试官喜欢看到这样的沟通：

"这道题要找两数之和等于target..."

"暴力解法是双重循环，时间复杂度O(n²)..."

"但如果用哈希表存储已遍历的数字，遍历时查找complement，
就能优化到O(n)..."

"空间复杂度会从O(1)增加到O(n)，这是用空间换时间..."

考察点三：应变能力

面试官经常会追问：

如果数据量是10亿呢？（考察分布式思维）
如果允许有重复元素呢？（考察边界情况处理）
如果内存只有1MB呢？（考察时空权衡）

能回答这些追问，才能拿到高分。

二、时间复杂度：决定代码生死的数字

很多人能写出代码，但说不清复杂度。这在面试中是致命伤。

常见复杂度一览

复杂度	别名	典型场景	n=100万时的操作数
O(1)	常数	哈希表查找、数组下标访问	1
O(log n)	对数	二分查找、平衡树	20
O(n)	线性	一次遍历	100万
O(n log n)	线性对数	快排、归并排序	2000万
O(n²)	平方	双重循环	1万亿 ❌
O(2ⁿ)	指数	暴力递归	无穷大 ❌

面试时的黄金法则：

10^6 以内用 O(n)
10^7 以内用 O(n log n)
10^8 以上必须 O(n) 或更优

怎么快速判断复杂度

规则1：看循环嵌套

// O(n) - 一层循环
for i := 0; i < n; i++ {
    // O(1)操作
}

// O(n²) - 两层嵌套
for i := 0; i < n; i++ {
    for j := 0; j < n; j++ {
        // O(1)操作
    }
}

// O(n log n) - 一层循环套二分
for i := 0; i < n; i++ {
    binarySearch(arr, target) // O(log n)
}

规则2：看递归深度

// 二分查找：每次减半，深度 log n，每层 O(1)
// 总复杂度：O(log n)
func binarySearch(arr []int, target int) int {
    left, right := 0, len(arr)-1
    for left <= right {
        mid := left + (right-left)/2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}

// 斐波那契（无优化）：每次分两路，深度 n
// 总复杂度：O(2^n) 😱
func fib(n int) int {
    if n <= 1 {
        return n
    }
    return fib(n-1) + fib(n-2)
}

规则3：均摊分析

// 动态数组扩容：偶尔 O(n)，大部分 O(1)
// 均摊复杂度：O(1)
arr = append(arr, elem)

三、数据结构：选对工具解决问题

面试中80%的题目都可以用这5种数据结构解决。

1. 数组 Array

核心特性：

随机访问 O(1)
插入删除 O(n)（需要移动元素）

什么时候用：

需要频繁按下标访问
数据大小固定或变化不大

高频题型：

双指针（两数之和、三数之和）
滑动窗口（最长子串、最小覆盖子串）
前缀和（子数组和、区间查询）

经典题目 - 两数之和：

// 题目：找出数组中两个数，使它们的和等于target
// 返回它们的下标

func twoSum(nums []int, target int) []int {
    // 哈希表存储：数值 -> 下标
    seen := make(map[int]int)

    for i, num := range nums {
        // 计算需要的另一个数
        complement := target - num

        // 检查这个数是否已经出现过
        if j, exists := seen[complement]; exists {
            return []int{j, i}
        }

        // 记录当前数字和下标
        seen[num] = i
    }

    return nil
}

// 面试追问：如果要返回所有组合呢？
// 答：用哈希表存储列表，处理重复值的情况

2. 链表 Linked List

核心特性：

随机访问 O(n)
已知位置插入删除 O(1)

什么时候用：

需要频繁在中间插入删除
不需要随机访问

高频题型：

反转链表
快慢指针（找环、找中点）
合并链表

经典题目 - 反转链表：

type ListNode struct {
    Val  int
    Next *ListNode
}

// 迭代版本 - 面试时推荐，不容易栈溢出
func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    curr := head

    for curr != nil {
        next := curr.Next  // 先保存下一个节点
        curr.Next = prev   // 反转指针
        prev = curr        // prev 前进
        curr = next        // curr 前进
    }

    return prev
}

// 面试官追问：能用递归实现吗？
func reverseListRecursive(head *ListNode) *ListNode {
    // 递归终止：空节点或只有一个节点
    if head == nil || head.Next == nil {
        return head
    }

    // 递归反转后面的链表
    newHead := reverseListRecursive(head.Next)

    // 把当前节点接到反转后链表的尾部
    head.Next.Next = head
    head.Next = nil

    return newHead
}

快慢指针 - 检测环：

func hasCycle(head *ListNode) bool {
    if head == nil {
        return false
    }

    slow, fast := head, head

    for fast != nil && fast.Next != nil {
        slow = slow.Next      // 慢指针走一步
        fast = fast.Next.Next // 快指针走两步

        if slow == fast {
            return true // 相遇说明有环
        }
    }

    return false
}

// 面试追问：如果有环，找到入口点？
func detectCycle(head *ListNode) *ListNode {
    slow, fast := head, head

    // 第一步：快慢指针找相遇点
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            break
        }
    }

    if fast == nil || fast.Next == nil {
        return nil // 无环
    }

    // 第二步：一个从head出发，一个从相遇点出发
    // 相遇点就是入口
    slow = head
    for slow != fast {
        slow = slow.Next
        fast = fast.Next
    }

    return slow
}

3. 哈希表 Hash Map

核心特性：

查找、插入、删除 O(1) 平均
不保证顺序

什么时候用：

需要快速查找
统计频次
缓存计算结果

高频题型：

两数之和系列
字符串匹配（变位词）
LRU缓存

经典题目 - LRU缓存（面试超高频）：

// 这题考察：哈希表 + 双向链表的组合使用
// 难度：Medium，但在面试中经常出现

type LRUCache struct {
    capacity int
    cache    map[int]*DLinkedNode // 哈希表快速查找
    head     *DLinkedNode          // 虚拟头节点
    tail     *DLinkedNode          // 虚拟尾节点
}

type DLinkedNode struct {
    key, value int
    prev, next *DLinkedNode
}

func Constructor(capacity int) LRUCache {
    l := LRUCache{
        capacity: capacity,
        cache:    make(map[int]*DLinkedNode),
        head:     &DLinkedNode{},
        tail:     &DLinkedNode{},
    }
    l.head.next = l.tail
    l.tail.prev = l.head
    return l
}

func (l *LRUCache) Get(key int) int {
    if node, ok := l.cache[key]; ok {
        // 访问了，移到头部（最近使用）
        l.moveToHead(node)
        return node.value
    }
    return -1
}

func (l *LRUCache) Put(key int, value int) {
    if node, ok := l.cache[key]; ok {
        // key存在，更新值并移到头部
        node.value = value
        l.moveToHead(node)
    } else {
        // key不存在，新建节点
        newNode := &DLinkedNode{key: key, value: value}
        l.cache[key] = newNode
        l.addToHead(newNode)

        // 超过容量，删除尾部节点（最久未使用）
        if len(l.cache) > l.capacity {
            removed := l.removeTail()
            delete(l.cache, removed.key)
        }
    }
}

// 辅助方法
func (l *LRUCache) addToHead(node *DLinkedNode) {
    node.prev = l.head
    node.next = l.head.next
    l.head.next.prev = node
    l.head.next = node
}

func (l *LRUCache) removeNode(node *DLinkedNode) {
    node.prev.next = node.next
    node.next.prev = node.prev
}

func (l *LRUCache) moveToHead(node *DLinkedNode) {
    l.removeNode(node)
    l.addToHead(node)
}

func (l *LRUCache) removeTail() *DLinkedNode {
    node := l.tail.prev
    l.removeNode(node)
    return node
}

4. 栈 Stack

核心特性：

后进先出（LIFO）
只能从栈顶操作

什么时候用：

括号匹配
表达式求值
单调栈（下一个更大元素）

经典题目 - 有效括号：

func isValid(s string) bool {
    stack := []rune{}
    pairs := map[rune]rune{
        ')': '(',
        ']': '[',
        '}': '{',
    }

    for _, char := range s {
        // 左括号入栈
        if char == '(' || char == '[' || char == '{' {
            stack = append(stack, char)
        } else {
            // 右括号：检查栈顶是否匹配
            if len(stack) == 0 || stack[len(stack)-1] != pairs[char] {
                return false
            }
            stack = stack[:len(stack)-1] // 弹出栈顶
        }
    }

    return len(stack) == 0 // 栈空说明全部匹配
}

单调栈 - 每日温度：

// 题目：给定温度数组，返回每天需要等多少天才会有更高温度

func dailyTemperatures(temperatures []int) []int {
    n := len(temperatures)
    result := make([]int, n)
    stack := []int{} // 存储下标，保持对应温度单调递减

    for i := 0; i < n; i++ {
        // 当前温度比栈顶高，说明栈顶元素找到了答案
        for len(stack) > 0 && temperatures[i] > temperatures[stack[len(stack)-1]] {
            prevIdx := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            result[prevIdx] = i - prevIdx
        }
        stack = append(stack, i)
    }

    return result
}

5. 队列 Queue

核心特性：

先进先出（FIFO）
两端操作

什么时候用：

BFS 广度优先搜索
滑动窗口（用双端队列）

经典题目 - 二叉树层序遍历：

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }

    result := [][]int{}
    queue := []*TreeNode{root}

    for len(queue) > 0 {
        levelSize := len(queue) // 当前层的节点数
        level := []int{}

        // 处理当前层的所有节点
        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:] // 出队

            level = append(level, node.Val)

            // 子节点入队（下一层）
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }

        result = append(result, level)
    }

    return result
}

四、选择数据结构的决策树

面试时遇到问题，按这个思路选择：

                 需要什么操作？
                      │
        ┌─────────────┼─────────────┐
        │             │             │
    快速查找    保持顺序/排序    模拟过程
        │             │             │
    哈希表        ┌────┴────┐    ┌──┴──┐
                 │         │    │     │
              有序数组    树   栈     队列
              (二分)          (括号)  (BFS)

实战例子：

问题	选择	原因
两数之和	哈希表	需要快速查找补数
排序后的数组查找	二分	有序 + 快速查找
括号匹配	栈	后进先出特性
层序遍历	队列	按层处理，先进先出
前K大元素	堆	维护有序的前K个

五、刷题策略：效率比数量更重要

如何高效刷题

错误做法：

看题5分钟就看答案
刷完就过，不复盘
只追求数量，不总结套路

正确做法：

1. 先思考15-20分钟，想到思路再写
2. 写完后分析复杂度，思考是否有更优解
3. 记录解题思路，过几天再做一遍
4. 同类型题目放一起，总结模板

必背模板

二分查找模板：

func binarySearch(nums []int, target int) int {
    left, right := 0, len(nums)-1

    for left <= right {
        mid := left + (right-left)/2 // 防止溢出

        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return -1
}

BFS模板：

func bfs(start Node) {
    queue := []Node{start}
    visited := make(map[Node]bool)
    visited[start] = true

    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]

        // 处理当前节点
        process(node)

        // 将相邻节点加入队列
        for _, neighbor := range node.neighbors {
            if !visited[neighbor] {
                visited[neighbor] = true
                queue = append(queue, neighbor)
            }
        }
    }
}

DFS模板：

func dfs(node Node, visited map[Node]bool) {
    if node == nil || visited[node] {
        return
    }

    visited[node] = true
    process(node)

    for _, neighbor := range node.neighbors {
        dfs(neighbor, visited)
    }
}

六、面试中常犯的错误

错误1：上来就写代码

正确做法： 先和面试官确认理解是否正确

"让我确认一下，输入是一个整数数组..."
"数组元素可以重复吗？"
"数据范围大概是多少？10^6 级别吗？"

错误2：只想到暴力解

正确做法： 先说暴力解，再优化

"暴力解法是O(n²)，遍历所有组合..."
"但如果用哈希表存储已遍历的元素..."
"可以优化到O(n)，空间复杂度增加到O(n)..."

错误3：代码写完就结束

正确做法： 主动测试

"我用这个用例走一遍：[2, 7, 11, 15], target=9..."
"边界情况：空数组会返回nil..."
"再测一个无解的情况..."

七、本章小结

一张图总结算法面试：

             ┌─────────────────────┐
             │   面试官在考察什么？   │
             └─────────────────────┘
                       │
         ┌─────────────┼─────────────┐
         │             │             │
    ┌────┴────┐   ┌────┴────┐   ┌────┴────┐
    │ 编码能力 │   │ 思考过程 │   │ 沟通表达 │
    └─────────┘   └─────────┘   └─────────┘
         │             │             │
    代码规范      说清思路       主动沟通
    边界处理      分析复杂度     确认理解
    测试意识      权衡方案       解释决策

记住这三点：

面试不是默写答案，是展示思考过程
复杂度分析是必考点，要能脱口而出
数据结构的选择比算法技巧更重要

下期预告

《双指针与滑动窗口：一个套路解决10道高频题》

内容预告：

双指针的三种类型
滑动窗口的万能模板
实战：三数之和、最长无重复子串

关注公众号，明天见👆

你觉得最难的算法类型是什么？欢迎在评论区留言，高赞问题会在后续详细讲解。