算法面试高频题：数组、树与动态规划
算法面试高频题：数组、树与动态规划
本教程精选大厂面试中命中率最高的算法题型，围绕数组、二叉树和动态规划三大核心专题展开。每个考点配套解题模板、复杂度分析与可运行代码，帮你用最短时间突破算法面试。
数组篇
数组是数据结构的基础，面试中常考察：双指针、前缀和、哈希表、排序思想以及原地操作等技巧。
1. 两数之和（Two Sum）
题目
给定一个整数数组 nums 和一个目标值 target，找出数组中和为目标值的两个数的下标。假设每种输入只会对应一个答案，且同一元素不能使用两遍。
分析
暴力双重循环会超时。空间换时间：遍历时用哈希表存储已经访问过的数值与下标，对于当前数 x，检查 target - x 是否在哈希表中。
复杂度
- 时间：O(n)
- 空间：O(n)
代码示例（Python）
def twoSum(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
2. 三数之和（3Sum）
题目
判断数组 nums 中是否存在三个元素 a, b, c，使得 a + b + c = 0。找出所有不重复的三元组。
分析
先排序，然后固定一个数，剩余部分转化为两数之和问题，使用双指针从两边向中间逼近。注意跳过重复元素以避免重复解。
复杂度
- 时间：O(n²)
- 空间：O(1)（不计结果存储）
代码示例（Python）
def threeSum(nums):
nums.sort()
res = []
n = len(nums)
for i in range(n - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, n - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
res.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
return res
3. 最大子数组和（Maximum Subarray）
题目
给定整数数组，找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
分析
经典 Kadane 算法：设 dp[i] 为以 i 结尾的最大子数组和，则有 dp[i] = max(nums[i], dp[i-1] + nums[i])。由于只依赖前一个状态，可压缩为变量 cur_sum。
复杂度
- 时间：O(n)
- 空间：O(1)
代码示例（Python）
def maxSubArray(nums):
max_sum = nums[0]
cur_sum = nums[0]
for i in range(1, len(nums)):
cur_sum = max(nums[i], cur_sum + nums[i])
max_sum = max(max_sum, cur_sum)
return max_sum
4. 合并区间（Merge Intervals）
题目
以数组 intervals 表示若干个区间的集合，合并所有重叠的区间。
分析
先按区间起点排序，然后遍历：如果当前区间与结果集中最后一个区间重叠（即当前起点 ≤ 上一个终点），则更新上一个终点为两者终点的较大值；否则直接加入。
复杂度
- 时间：O(n log n)（排序）
- 空间：O(n)（输出）
代码示例（Python）
def merge(intervals):
intervals.sort(key=lambda x: x[0])
merged = []
for interval in intervals:
if not merged or merged[-1][1] < interval[0]:
merged.append(interval)
else:
merged[-1][1] = max(merged[-1][1], interval[1])
return merged
5. 缺失的第一个正数（First Missing Positive）
题目
给定一个未排序的整数数组，找出其中没有出现的最小的正整数。要求时间复杂度 O(n)，空间复杂度 O(1)。
分析
原地哈希：将数字放到正确的位置上，即数字 x 应当位于下标 x-1（对于 1 ≤ x ≤ n）。通过多次交换使得数组呈现索引与值的对应关系，最后遍历找出第一个不匹配的位置。
复杂度
- 时间：O(n)
- 空间：O(1)
代码示例（Python）
def firstMissingPositive(nums):
n = len(nums)
for i in range(n):
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
for i in range(n):
if nums[i] != i + 1:
return i + 1
return n + 1
树篇
二叉树问题通常考察递归（DFS）和层序遍历（BFS），还常涉及搜索树性质、路径与祖先等。
1. 二叉树的最大深度
题目
给定一棵二叉树，求其最大深度（根节点到最远叶子节点的最长路径上的节点数）。
分析
标准递归：深度 = 1 + max(左子树深度, 右子树深度)。终止条件为空节点返回 0。
复杂度
- 时间：O(n)
- 空间：O(h)，h 为树高（递归栈深度）
代码示例（Python）
def maxDepth(root):
if not root:
return 0
return 1 + max(maxDepth(root.left), maxDepth(root.right))
2. 验证二叉搜索树（Validate BST）
题目
判断给定的二叉树是否是一棵有效的二叉搜索树（BST）。有效 BST 定义：左子树所有节点值 < 根节点值 < 右子树所有节点值，且左右子树也必须是 BST。
分析
递归时携带允许的取值范围 (low, high)。对于节点值 val，必须满足 low < val < high。向左走时更新上界，向右走时更新下界。
复杂度
- 时间：O(n)
- 空间：O(h)
代码示例（Python）
def isValidBST(root):
def helper(node, low, high):
if not node:
return True
if not (low < node.val < high):
return False
return helper(node.left, low, node.val) and helper(node.right, node.val, high)
return helper(root, float('-inf'), float('inf'))
3. 二叉树的层序遍历
题目
返回二叉树按层遍历得到的节点值（即逐层从左到右，每层作为一个列表）。
分析
使用队列进行 BFS。每次处理当前队列中所有节点（代表同一层），并将它们的子节点加入下一层队列。
复杂度
- 时间：O(n)
- 空间：O(n)（队列最大宽度）
代码示例（Python）
from collections import deque
def levelOrder(root):
if not root:
return []
res, q = [], deque([root])
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
res.append(level)
return res
4. 二叉树的最近公共祖先
题目
找出一棵二叉树中两个指定节点的最近公共祖先（LCA）。
分析
后序遍历递归：如果当前节点是 p 或 q，直接返回；否则分别在左右子树中查找。若左右各返回非空，则当前节点为 LCA；若只有一侧非空，则那一侧的返回结果就是 LCA。
复杂度
- 时间：O(n)
- 空间：O(h)
代码示例（Python）
def lowestCommonAncestor(root, p, q):
if not root or root == p or root == q:
return root
left = lowestCommonAncestor(root.left, p, q)
right = lowestCommonAncestor(root.right, p, q)
if left and right:
return root
return left if left else right
5. 路径总和 II（返回所有路径）
题目
给定二叉树和一个目标和 targetSum，找出所有从根节点到叶子节点路径总和等于给定值的路径。
分析
DFS 回溯：沿路径累加当前和，到达叶子时检查是否等于目标和，若是则保存路径。注意路径恢复（回溯）。
复杂度
- 时间：O(n²)（最坏情况每条路径都复制）
- 空间：O(h)
代码示例（Python）
def pathSum(root, targetSum):
res, path = [], []
def dfs(node, cur_sum):
if not node:
return
path.append(node.val)
cur_sum += node.val
if not node.left and not node.right and cur_sum == targetSum:
res.append(list(path))
else:
dfs(node.left, cur_sum)
dfs(node.right, cur_sum)
path.pop()
dfs(root, 0)
return res
动态规划篇
动态规划的核心是状态定义和状态转移。面试中常考线性、区间、背包及字符串编辑等模型。
1. 爬楼梯（Climbing Stairs）
题目
假设你正在爬楼梯，需要 n 阶才能到达楼顶。每次可以爬 1 或 2 个台阶，有多少种不同的方法可以爬到楼顶？
分析
dp[i] = 到达第 i 阶的方法数，dp[i] = dp[i-1] + dp[i-2]。初值 dp[0]=1, dp[1]=1。可用滚动变量优化空间。
复杂度
- 时间：O(n)
- 空间：O(1)
代码示例（Python）
def climbStairs(n):
a, b = 1, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
2. 打家劫舍（House Robber）
题目
沿街房屋，每间房内藏有一定现金，相邻的房屋装有防盗系统，如果两间相邻的房屋在同一晚上被闯入，系统会自动报警。计算不触动警报的情况下，一夜之内能偷窃到的最高金额。
分析
dp[i] = 偷前 i 间房的最大收益。决定偷或不偷当前房屋：dp[i] = max(dp[i-1], dp[i-2] + nums[i])。同样可以压缩状态。
复杂度
- 时间：O(n)
- 空间：O(1)
代码示例（Python）
def rob(nums):
prev2, prev1 = 0, 0
for num in nums:
cur = max(prev1, prev2 + num)
prev2, prev1 = prev1, cur
return prev1
3. 最长递增子序列（LIS）
题目
给定整数数组，找到其中最长严格递增子序列的长度。
分析
解法一：dp[i] 表示以 i 结尾的最长递增子序列长度，dp[i] = max(dp[j] + 1) 其中 j < i 且 nums[j] < nums[i]。O(n²) 时间。
进阶思路：维护一个 tails 数组，tails[k] 表示长度为 k+1 的递增子序列的最小结尾数字。用二分查找更新，可 O(n log n)。
复杂度（最优）
- 时间：O(n log n)
- 空间：O(n)
代码示例（Python，O(n log n)）
import bisect
def lengthOfLIS(nums):
tails = []
for x in nums:
pos = bisect.bisect_left(tails, x)
if pos == len(tails):
tails.append(x)
else:
tails[pos] = x
return len(tails)
4. 零钱兑换（Coin Change）
题目
给定不同面额的硬币 coins 和一个总金额 amount，计算可以凑成总金额所需的最少的硬币个数。如果无法凑出，返回 -1。
分析
dp[i] 表示凑出金额 i 所需的最少硬币数。初始化 dp[0]=0，其余为 amount+1 表示不可达。转移：dp[i] = min(dp[i], dp[i-coin] + 1) 对所有 coin ≤ i。
复杂度
- 时间：O(n * amount)，n 为硬币种类数
- 空间：O(amount)
代码示例（Python）
def coinChange(coins, amount):
MAX = amount + 1
dp = [MAX] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != MAX else -1
5. 编辑距离（Edit Distance）
题目
给定两个单词 word1 和 word2，计算将 word1 转换成 word2 所使用的最少操作数。允许的操作：插入一个字符、删除一个字符、替换一个字符。
分析
dp[i][j] 表示 word1 前 i 个字符转换为 word2 前 j 个字符的最小操作数。
若 word1[i-1] == word2[j-1]，则 dp[i][j] = dp[i-1][j-1]；
否则 dp[i][j] = 1 + min(dp[i-1][j] (删除), dp[i][j-1] (插入), dp[i-1][j-1] (替换))。
复杂度
- 时间：O(m * n)
- 空间：O(m * n)，可优化为 O(n)
代码示例（Python）
def minDistance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
return dp[m][n]
以上所有题目均覆盖了阿里、字节、腾讯等大厂算法面试的高频考点，建议每道题都手写三遍以上，理解思路并能秒写最优解。