算法面试题型与解题思路

更新: 5/15/2026 字数: 0 字时长: 0 分钟

社招面试中算法题以 LeetCode Medium 为主，偶尔 Easy/Hard。重点不是刷题量，而是掌握每种题型的核心思路和模板。

1. 数组与双指针

核心思路

左右指针：从两端向中间逼近，常用于有序数组、容器盛水类问题
快慢指针：一快一慢，用于链表环检测、删除倒数第 N 个节点
滑动窗口：维护一个窗口 [left, right)，right 扩张、left 收缩，用于子串/子数组问题

滑动窗口模板

java

int left = 0;
Map<Character, Integer> window = new HashMap<>();

for (int right = 0; right < s.length(); right++) {
    char c = s.charAt(right);
    window.merge(c, 1, Integer::sum); // 扩张：加入右边元素

    while (窗口需要收缩) {
        char d = s.charAt(left);
        window.merge(d, -1, Integer::sum); // 收缩：移除左边元素
        left++;
    }
    // 在这里更新结果
}

经典题目

题目	思路	难度
两数之和	HashMap 存已遍历的值	Easy
三数之和	排序 + 固定一个数 + 左右指针	Medium
盛最多水的容器	左右指针，移动较短的一边	Medium
无重复字符的最长子串	滑动窗口 + HashSet	Medium
最小覆盖子串	滑动窗口 + 计数器	Hard
合并区间	按起点排序，逐个合并	Medium
下一个排列	从右找第一个降序位，交换后翻转	Medium

2. 链表

核心思路

虚拟头节点（dummy）：简化头节点的边界处理
快慢指针：找中点、判环、找环入口
反转链表：迭代（prev/curr/next 三指针）或递归
合并链表：归并思想

反转链表模板

java

ListNode prev = null, curr = head;
while (curr != null) {
    ListNode next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
}
return prev;

经典题目

题目	思路	难度
反转链表	三指针迭代	Easy
反转链表 II（区间反转）	找到区间，断开反转再接回	Medium
合并两个有序链表	dummy + 逐个比较	Easy
合并 K 个有序链表	小顶堆 / 分治归并	Hard
环形链表 II	快慢指针相遇后，头和相遇点同速走	Medium
LRU 缓存	HashMap + 双向链表	Medium
相交链表	两指针各走一遍对方的路	Easy
K 个一组翻转链表	分组 + 组内反转 + 拼接	Hard

3. 哈希表

核心思路

用空间换时间，O(1) 查找
计数：统计频率、判断异位词
映射：两数之和、字符对应关系
去重：判断是否出现过

经典题目

题目	思路	难度
两数之和	遍历时查 HashMap	Easy
字母异位词分组	排序后的字符串作为 key	Medium
最长连续序列	HashSet + 只从起点开始计数	Medium
前 K 个高频元素	HashMap 计数 + 小顶堆/桶排序	Medium

4. 栈与队列

核心思路

单调栈：维护一个单调递增/递减的栈，用于"下一个更大/更小元素"类问题
辅助栈：括号匹配、表达式求值、最小栈
栈模拟：DFS、路径简化

单调栈模板（下一个更大元素）

java

int[] result = new int[nums.length];
Deque<Integer> stack = new ArrayDeque<>(); // 存下标

for (int i = nums.length - 1; i >= 0; i--) {
    while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) {
        stack.pop(); // 弹出比当前小的
    }
    result[i] = stack.isEmpty() ? -1 : nums[stack.peek()];
    stack.push(i);
}

经典题目

题目	思路	难度
有效的括号	栈匹配	Easy
每日温度	单调递减栈	Medium
柱状图中最大的矩形	单调递增栈，找左右边界	Hard
最小栈	辅助栈同步记录最小值	Medium
接雨水	单调栈 / 双指针 / 动态规划	Hard
字符串解码	双栈（数字栈 + 字符串栈）	Medium

5. 二叉树

核心思路

递归三要素：①返回值和参数 ②终止条件 ③单层逻辑
遍历方式：前序（根左右）、中序（左根右）、后序（左右根）、层序（BFS）
分治思想：把问题拆成左子树和右子树分别解决，再合并结果

递归模板

java

// 自顶向下（传参数下去）
void traverse(TreeNode node, int depth) {
    if (node == null) return;
    // 前序位置：处理当前节点
    traverse(node.left, depth + 1);
    // 中序位置
    traverse(node.right, depth + 1);
    // 后序位置
}

// 自底向上（收集返回值）
int maxDepth(TreeNode node) {
    if (node == null) return 0;
    int left = maxDepth(node.left);
    int right = maxDepth(node.right);
    return Math.max(left, right) + 1; // 后序位置合并结果
}

经典题目

题目	思路	难度
二叉树的最大深度	递归：max(左, 右) + 1	Easy
翻转二叉树	递归交换左右子树	Easy
对称二叉树	双指针递归比较	Easy
二叉树的层序遍历	BFS + 队列	Medium
从前序与中序构造二叉树	前序第一个是根，中序分左右	Medium
二叉树的最近公共祖先	后序遍历，左右子树分别找	Medium
二叉树的直径	后序遍历，每个节点算左+右深度	Easy
验证二叉搜索树	中序遍历递增 / 递归传上下界	Medium
二叉树的序列化与反序列化	前序遍历 + null 标记	Hard
二叉树中的最大路径和	后序遍历，维护全局最大值	Hard

6. 二叉搜索树（BST）

核心性质

左子树所有节点 < 根 < 右子树所有节点
中序遍历是有序的（这是解题关键）

经典题目

题目	思路	难度
验证二叉搜索树	中序遍历递增 / 递归传范围	Medium
二叉搜索树中第 K 小的元素	中序遍历到第 K 个	Medium
将有序数组转换为 BST	取中间元素为根，递归建树	Easy
删除 BST 中的节点	找后继节点替换	Medium

7. 回溯（Backtracking）

核心思路

回溯 = DFS + 撤销选择。本质是在决策树上穷举所有路径。

做选择 → 递归进入下一层 → 撤销选择

回溯模板

java

List<List<Integer>> result = new ArrayList<>();

void backtrack(int[] nums, List<Integer> path, boolean[] used) {
    if (满足结束条件) {
        result.add(new ArrayList<>(path)); // 注意拷贝
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;          // 剪枝
        path.add(nums[i]);              // 做选择
        used[i] = true;
        backtrack(nums, path, used);    // 递归
        path.remove(path.size() - 1);   // 撤销选择
        used[i] = false;
    }
}

去重技巧

排列/组合中有重复元素时：先排序，然后 if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;

经典题目

题目	思路	难度
全排列	回溯 + used 数组	Medium
全排列 II（有重复）	排序 + 去重剪枝	Medium
子集	每个元素选或不选	Medium
组合总和	回溯 + 可重复选（i 不加 1）	Medium
组合总和 II（不可重复）	排序 + 去重 + i+1	Medium
N 皇后	回溯 + 列/对角线冲突检测	Hard
电话号码的字母组合	回溯，每层对应一个数字的字母	Medium
括号生成	回溯，左括号数 ≥ 右括号数	Medium
单词搜索	二维网格 DFS 回溯	Medium

8. 动态规划（DP）

核心思路

定义状态：dp[i] 或 dp[i][j] 代表什么
状态转移方程：dp[i] 怎么从之前的状态推导出来
初始条件：dp[0] 或 dp[0][0] 是什么
遍历顺序：确保计算 dp[i] 时所依赖的状态已经算好

常见 DP 类型

8.1 线性 DP

dp[i] = f(dp[i-1], dp[i-2], ...)

题目	状态定义	转移方程	难度
爬楼梯	dp[i] = 到第 i 阶的方法数	dp[i] = dp[i-1] + dp[i-2]	Easy
打家劫舍	dp[i] = 前 i 家最大金额	dp[i] = max(dp[i-1], dp[i-2]+nums[i])	Medium
最长递增子序列	dp[i] = 以 i 结尾的 LIS 长度	dp[i] = max(dp[j]+1)，j < i 且 nums[j] < nums[i]	Medium
最大子数组和	dp[i] = 以 i 结尾的最大和	dp[i] = max(nums[i], dp[i-1]+nums[i])	Medium
解码方法	dp[i] = 前 i 个字符的解码数	dp[i] = dpi-1 + dpi-2	Medium

8.2 二维 DP / 网格 DP

dp[i][j] = f(dp[i-1][j], dp[i][j-1], ...)

题目	状态定义	转移方程	难度
不同路径	dp[i][j] = 到 (i,j) 的路径数	dp[i][j] = dp[i-1][j] + dp[i][j-1]	Medium
最小路径和	dp[i][j] = 到 (i,j) 的最小和	dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]	Medium
编辑距离	dp[i][j] = word1 前 i 个变成 word2 前 j 个的最少操作	相等跳过，不等取 min(增删改)+1	Hard
最长公共子序列	dp[i][j] = 前 i 和前 j 的 LCS 长度	相等 dp[i-1][j-1]+1，不等 max(dp[i-1][j], dp[i][j-1])	Medium

8.3 背包 DP

0-1 背包：每个物品只能选一次
完全背包：每个物品可以选无限次

java

// 0-1 背包（一维优化，逆序遍历）
for (int i = 0; i < n; i++) {
    for (int j = W; j >= weight[i]; j--) {
        dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

// 完全背包（正序遍历）
for (int i = 0; i < n; i++) {
    for (int j = weight[i]; j <= W; j++) {
        dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

题目	背包类型	难度
分割等和子集	0-1 背包（目标 sum/2）	Medium
零钱兑换	完全背包（求最少硬币数）	Medium
零钱兑换 II	完全背包（求组合数）	Medium
目标和	0-1 背包（转化为子集和问题）	Medium
单词拆分	完全背包变体	Medium

8.4 区间 DP

dp[i][j] = 区间 [i, j] 上的最优解
枚举分割点 k：dp[i][j] = f(dp[i][k], dp[k+1][j])

题目	思路	难度
最长回文子串	dp[i][j] = s[i..j] 是否回文	Medium
戳气球	区间 DP，枚举最后戳的气球	Hard

9. 贪心

核心思路

每一步都做局部最优选择，期望得到全局最优。关键是证明贪心策略的正确性。

经典题目

题目	贪心策略	难度
买卖股票的最佳时机 II	只要明天涨就今天买	Medium
跳跃游戏	维护能到达的最远位置	Medium
跳跃游戏 II	每步跳到能到最远的位置	Medium
分发糖果	左右各扫一遍取 max	Hard
无重叠区间	按结束时间排序，贪心选不重叠的	Medium
划分字母区间	记录每个字母最后出现位置	Medium

10. BFS / DFS（图与网格搜索）

BFS 模板（层序遍历 / 最短路径）

java

Queue<int[]> queue = new LinkedList<>();
boolean[][] visited = new boolean[m][n];
queue.offer(new int[]{startX, startY});
visited[startX][startY] = true;
int step = 0;

while (!queue.isEmpty()) {
    int size = queue.size();
    for (int i = 0; i < size; i++) {
        int[] curr = queue.poll();
        if (curr 是目标) return step;

        for (int[] dir : directions) { // {{0,1},{0,-1},{1,0},{-1,0}}
            int nx = curr[0] + dir[0], ny = curr[1] + dir[1];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
                visited[nx][ny] = true;
                queue.offer(new int[]{nx, ny});
            }
        }
    }
    step++;
}

经典题目

题目	思路	难度
岛屿数量	DFS/BFS 遍历连通区域	Medium
岛屿的最大面积	DFS 计数	Medium
腐烂的橘子	多源 BFS	Medium
课程表（拓扑排序）	BFS + 入度表	Medium
课程表 II	拓扑排序输出顺序	Medium
单词接龙	BFS 最短路径	Hard

11. 二分查找

核心思路

有序 + 查找 → 二分。关键是确定搜索区间和边界条件。

三种模板

java

// 1. 标准二分：找 target
int left = 0, right = nums.length - 1;
while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) return mid;
    else if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
}

// 2. 左边界：找第一个 >= target 的位置
int left = 0, right = nums.length - 1;

while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] < target) {
        left = mid + 1;   // 不够大，往右走
    } else {
        right = mid - 1;  // 太大或相等，往左找更早的
    }
}

return left; // 最终 left 就是第一个 ≥ target 的下标

// 3. 右边界：找最后一个 <= target 的位置
int left = 0, right = nums.length - 1;

while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] > target) {
        right = mid - 1;  // 太大，往左走
    } else {
        left = mid + 1;   // 太小或相等，往右找更晚的
    }
}

return right; // 最终 right 就是最后一个 ≤ target 的下标

经典题目

题目	思路	难度
搜索旋转排序数组	二分，判断哪半边有序	Medium
在排序数组中查找元素的第一个和最后一个位置	两次二分找左右边界	Medium
搜索二维矩阵	展开为一维二分 / 右上角搜索	Medium
寻找旋转排序数组中的最小值	二分，和右端点比较	Medium
寻找两个正序数组的中位数	二分找分割线	Hard

12. 堆（优先队列）

核心思路

Top K 问题：用大小为 K 的小顶堆
合并 K 个有序序列：小顶堆维护每个序列的当前最小值
动态中位数：大顶堆（左半）+ 小顶堆（右半）

经典题目

题目	思路	难度
前 K 个高频元素	HashMap 计数 + 小顶堆	Medium
数组中的第 K 个最大元素	小顶堆 / 快速选择	Medium
合并 K 个升序链表	小顶堆	Hard
数据流的中位数	大顶堆 + 小顶堆	Hard

13. 前缀和 / 差分

前缀和

java

// 构建前缀和
int[] prefix = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
    prefix[i + 1] = prefix[i] + nums[i];
}
// 区间和 [i, j] = prefix[j+1] - prefix[i]

经典题目

题目	思路	难度
和为 K 的子数组	前缀和 + HashMap	Medium
除自身以外数组的乘积	左前缀积 × 右前缀积	Medium

14. 并查集（Union-Find）

模板

java

class UnionFind {
    int[] parent, rank;

    UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]); // 路径压缩
        return parent[x];
    }

    void union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return;
        if (rank[px] < rank[py]) { int t = px; px = py; py = t; }
        parent[py] = px; // 按秩合并
        if (rank[px] == rank[py]) rank[px]++;
    }
}

经典题目

题目	思路	难度
岛屿数量（并查集解法）	合并相邻陆地	Medium
冗余连接	加边时发现环	Medium

15. 字符串

经典题目

题目	思路	难度
最长回文子串	中心扩展 / DP	Medium
最长公共前缀	纵向比较	Easy
字符串转换整数 (atoi)	状态机 / 逐字符处理	Medium
实现 strStr()	KMP / 直接匹配	Easy

16. 位运算

常用技巧

n & (n - 1)    → 消除最低位的 1
n & (-n)       → 获取最低位的 1
a ^ a = 0      → 异或找唯一数

经典题目

题目	思路	难度
只出现一次的数字	全部异或	Easy
位 1 的个数	n & (n-1) 循环计数	Easy
2 的幂	n > 0 && (n & (n-1)) == 0	Easy

17. 设计题

题目	核心数据结构	难度
LRU 缓存	HashMap + 双向链表	Medium
LFU 缓存	HashMap + 频率桶（双向链表）	Hard
最小栈	辅助栈	Medium
用栈实现队列	两个栈	Easy

面试高频 Top 30（必刷）

按出现频率排序，这些题在社招面试中反复出现：

两数之和
反转链表
LRU 缓存
无重复字符的最长子串
合并两个有序链表
二叉树的层序遍历
最大子数组和
三数之和
买卖股票的最佳时机
岛屿数量
全排列
二叉树的最近公共祖先
搜索旋转排序数组
合并区间
爬楼梯
零钱兑换
有效的括号
接雨水
最长递增子序列
二叉树的最大深度
环形链表 II
每日温度
编辑距离
前 K 个高频元素
课程表
最小路径和
单词搜索
数组中的第 K 个最大元素
最长回文子串
K 个一组翻转链表

解题策略

面试中的做题流程

1. 理解题意（2 分钟）
   → 确认输入输出、边界条件、数据规模
   → 用例子验证理解

2. 说思路（3 分钟）
   → 先说暴力解法和复杂度
   → 再说优化思路
   → 和面试官确认方向

3. 写代码（15 分钟）
   → 先写主体逻辑，再处理边界
   → 变量命名清晰
   → 边写边解释

4. 测试（5 分钟）
   → 用示例 dry run 一遍
   → 考虑边界：空输入、单元素、全相同、最大值

看到题目的第一反应

有序数组/矩阵        → 二分查找
最优/最大/最小/最长   → DP 或贪心
所有方案/排列/组合    → 回溯
最短路径/层数        → BFS
连通性              → DFS / 并查集
Top K               → 堆
子串/子数组          → 滑动窗口 / 前缀和
树的问题            → 递归（想清楚用前序/中序/后序）

实习面试刷题重点

实习面试算法通常比社招系统设计更高频，建议先把 Easy 和常见 Medium 刷熟，重点练“边写边讲”和复杂度分析。

必须掌握的题型

题型	必刷能力	代表题
数组/哈希	下标、去重、计数、映射关系	两数之和、合并区间、前 K 个高频元素
字符串	字符计数、双指针、滑动窗口	有效括号、最长无重复子串、最长回文子串
链表	指针移动、反转、快慢指针	反转链表、合并两个有序链表、环形链表
栈/队列	匹配、单调栈、BFS	有效括号、每日温度、二叉树层序遍历
二叉树	递归、遍历、深度	最大深度、层序遍历、最近公共祖先
动态规划	状态定义、转移方程	爬楼梯、最大子数组和、买卖股票

实习面试答题模板

1. 先复述题意，确认输入输出和边界。
2. 先说最直接的思路，再说优化方式。
3. 写代码时主动解释关键变量含义。
4. 写完用一个普通用例和一个边界用例 dry run。
5. 最后说时间复杂度和空间复杂度。

Android 实习建议优先级

先刷数组、字符串、链表、栈队列，保证 Easy 稳定 AC。
再刷二叉树、滑动窗口、二分查找，掌握常见模板。
最后补基础 DP 和回溯，不要一开始死磕 Hard。
每道题都要能口述思路，面试时“沉默写代码”会明显扣分。

算法面试题型与解题思路 ​

1. 数组与双指针 ​

核心思路 ​

滑动窗口模板 ​

经典题目 ​

2. 链表 ​

核心思路 ​

反转链表模板 ​

经典题目 ​

3. 哈希表 ​

核心思路 ​

经典题目 ​

4. 栈与队列 ​

核心思路 ​

单调栈模板（下一个更大元素） ​

经典题目 ​

5. 二叉树 ​

核心思路 ​

递归模板 ​

经典题目 ​

6. 二叉搜索树（BST） ​

核心性质 ​

经典题目 ​

7. 回溯（Backtracking） ​

核心思路 ​

回溯模板 ​

去重技巧 ​

经典题目 ​

8. 动态规划（DP） ​

核心思路 ​

常见 DP 类型 ​

8.1 线性 DP ​

8.2 二维 DP / 网格 DP ​

8.3 背包 DP ​

8.4 区间 DP ​

9. 贪心 ​

核心思路 ​

经典题目 ​

10. BFS / DFS（图与网格搜索） ​

BFS 模板（层序遍历 / 最短路径） ​

经典题目 ​

11. 二分查找 ​

核心思路 ​

三种模板 ​

经典题目 ​

12. 堆（优先队列） ​

核心思路 ​

经典题目 ​

13. 前缀和 / 差分 ​

前缀和 ​

经典题目 ​

14. 并查集（Union-Find） ​

模板 ​

经典题目 ​

15. 字符串 ​

经典题目 ​

16. 位运算 ​

常用技巧 ​

经典题目 ​

17. 设计题 ​

面试高频 Top 30（必刷） ​

解题策略 ​

面试中的做题流程 ​

看到题目的第一反应 ​

实习面试刷题重点 ​

必须掌握的题型 ​

实习面试答题模板 ​

Android 实习建议优先级 ​

算法面试题型与解题思路

1. 数组与双指针

核心思路

滑动窗口模板

经典题目

2. 链表

核心思路

反转链表模板

经典题目

3. 哈希表

核心思路

经典题目

4. 栈与队列

核心思路

单调栈模板（下一个更大元素）

经典题目

5. 二叉树

核心思路

递归模板

经典题目

6. 二叉搜索树（BST）

核心性质

经典题目

7. 回溯（Backtracking）

核心思路

回溯模板

去重技巧

经典题目

8. 动态规划（DP）

核心思路

常见 DP 类型

8.1 线性 DP

8.2 二维 DP / 网格 DP

8.3 背包 DP

8.4 区间 DP

9. 贪心

核心思路

经典题目

10. BFS / DFS（图与网格搜索）

BFS 模板（层序遍历 / 最短路径）

经典题目

11. 二分查找

核心思路

三种模板

经典题目

12. 堆（优先队列）

核心思路

经典题目

13. 前缀和 / 差分

前缀和

经典题目

14. 并查集（Union-Find）

模板

经典题目

15. 字符串

经典题目

16. 位运算

常用技巧

经典题目

17. 设计题

面试高频 Top 30（必刷）

解题策略

面试中的做题流程

看到题目的第一反应

实习面试刷题重点

必须掌握的题型

实习面试答题模板

Android 实习建议优先级