算法与数据结构（四）：高频算法思想与 Java 实现
导语：这一篇是"解题套路库"。双指针、滑动窗口、前缀和解决线性扫描类问题；递归、分治、回溯解决枚举与拆分类问题；贪心与动态规划解决最优化问题。所有套路都配可运行的 Java 实现，并标注易错点。共 14 题。
一、双指针与滑动窗口
1. 什么是双指针？有哪些常见套路？
答： 双指针用两个下标变量代替嵌套循环，把 O(n²) 降到 O(n)。三种常见形态：
| 形态 | 移动方式 | 典型题目 |
|---|---|---|
| 对撞指针 | 一左一右向中间靠拢 | 两数之和（有序数组）、盛最多水的容器、反转字符串、回文判断 |
| 快慢指针 | 同向，速度不同 | 链表判环、找中点、删除倒数第 N 个、数组原地去重 |
| 同向双指针（滑动窗口） | 一前一后维护区间 | 最长无重复子串、最小覆盖子串 |
对撞指针示例（有序数组求两数之和，O(n)）：
public int[] twoSum(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) return new int[]{left, right};
else if (sum < target) left++; // 和太小 → 左指针右移（增大）
else right--; // 和太大 → 右指针左移（减小）
}
return new int[]{-1, -1};
}快慢指针示例（有序数组原地去重，返回新长度）：
public int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int slow = 0; // slow 指向已去重部分的最后一个位置
for (int fast = 1; fast < nums.length; fast++) {
if (nums[fast] != nums[slow]) { // 发现新值
nums[++slow] = nums[fast]; // 覆盖到 slow 的下一位
}
}
return slow + 1;
}为什么双指针能降复杂度：关键在于单调性——"左指针右移后，右指针不需要回退"。每次移动都能排除一批不可能的答案，两个指针各自最多走
n步，故总代价O(n)。没有单调性，双指针就不成立。
2. 什么是滑动窗口？如何求「最长无重复字符子串」？
答： 滑动窗口是同向双指针的特化形式，用 [left, right] 维护一个满足条件的连续区间，通过扩大右边界、收缩左边界来求解"最长/最短满足条件的子串/子数组"。
import java.util.HashMap;
import java.util.Map;
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> lastIndex = new HashMap<>(); // 字符 → 最近出现的下标
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (lastIndex.containsKey(c)) {
// 该字符已出现过：左边界跳到"上次出现位置 + 1"
// 用 max 是防止 left 回退（上次出现位置可能在 left 左边）
left = Math.max(left, lastIndex.get(c) + 1);
}
lastIndex.put(c, right);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}滑动窗口通用模板：
int left = 0;
for (int right = 0; right < n; right++) {
// 1. 把 s[right] 加入窗口
// 2. while (窗口不满足条件) { 把 s[left] 移出窗口; left++; }
// 3. 此时窗口满足条件，更新答案
}最易错的一点：
left = Math.max(left, ...)中的max不能省。若直接left = lastIndex.get(c) + 1，当下次出现位置在left左侧时会把窗口"拉回去"，导致长度算错。
3. 什么是前缀和？如何用它优化区间查询？
答： 前缀和预先计算 prefix[i] = nums[0] + ... + nums[i-1]，从而把区间求和从 O(n) 降到 O(1)。
int[] nums = {1, 2, 3, 4, 5};
// 构建：prefix 长度比 nums 多 1，prefix[0] = 0（天然处理边界）
int[] prefix = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
// 查询区间 [l, r] 的和：O(1)
int l = 1, r = 3;
int sum = prefix[r + 1] - prefix[l]; // (2+3+4) = 9两个进阶变体：
- 前缀和 + 哈希表：求"和为 K 的子数组个数"——遍历时把
prefix[i]存入哈希表并统计prefix[i] - K出现的次数，时间O(n)； - 二维前缀和：
sum[i][j]表示左上角到(i,j)的矩形和，用容斥原理查询任意子矩形：S = sum[r2][c2] - sum[r1-1][c2] - sum[r2][c1-1] + sum[r1-1][c1-1]。
适用信号：题目出现「子数组和」「区间和」「连续子序列」且要求多次查询时，优先考虑前缀和（或前缀和 + 哈希）。
对比：前缀和是预处理换查询（空间换时间）；差分数组是其镜像——用于区间批量加减、最后求整体的场景。
二、递归、分治与回溯
4. 递归的本质是什么？如何分析递归的时间复杂度？
答： 递归的本质是函数调用栈 + 问题规模的缩小，必须包含两个要素：
- 终止条件（base case）：否则无限递归导致
StackOverflowError； - 递推关系：把原问题分解为规模更小的同类子问题。
分析复杂度的两种方法：
| 方法 | 做法 | 例子 |
|---|---|---|
| 展开求和 | 写出每层代价，求和（等差/等比） | 快排：n + n/2 + n/4 + … = O(n)（平均） |
| 主定理（Master Theorem） | T(n) = a·T(n/b) + f(n)，比较 n^(log_b a) 与 f(n) | 归并：a=2, b=2, f(n)=O(n) → O(n log n) |
常见递归的复杂度：
- 二分查找：
T(n) = T(n/2) + O(1)→O(log n) - 归并/快排：
T(n) = 2T(n/2) + O(n)→O(n log n) - 斐波那契暴力递归：
T(n) = T(n-1) + T(n-2)→O(2ⁿ)（存在大量重复计算，是 DP 的引入动机）
空间代价常被忽略：递归的空间复杂度是递归栈深度。归并排序写"空间 O(n)"是因为辅助数组，但栈深度是
O(log n)；而快排最坏退化为链式递归时，栈深度可达O(n)——这也是快排要随机化基准的工程原因之一。
5. 什么是分治法？有哪些典型应用？
答： 分治（Divide and Conquer） 三步走：分解（Divide）→ 解决（Conquer，递归处理子问题）→ 合并（Combine，把子结果合成原问题的解）。
与递归的关系：分治是思想，递归是实现手段；分治要求子问题相互独立、互不重叠（若有重叠则应该用动态规划）。
| 算法 | 分解方式 | 合并方式 |
|---|---|---|
| 归并排序 | 按位置对半切 | 合并两个有序数组 |
| 快速排序 | 按基准值分区 | 无需合并（原地分区后即有序） |
| 二分查找 | 去掉一半 | 无需合并（只在单侧递归） |
| 大整数乘法 / 快速幂 | 按位拆 | 组合结果 |
| MapReduce / ForkJoinPool | 数据分片 | 汇总归约 |
对照记忆：分治适用"子问题不重叠"，动态规划适用"子问题重叠"。归并排序若改成"分别排序后还要处理跨区间的重复元素"，就变成了 DP 的形态。
6. 什么是回溯？回溯的通用模板是什么？
答： 回溯（Backtracking） 是带撤销操作的深度优先搜索：在决策树上一条路走到能判断结果为止，走不通就退回上一步、换下一个选择。
通用模板（务必背下来，一套模板能解几十道题）：
void backtrack(路径, 选择列表) {
if (满足结束条件) {
记录结果; // 通常是 path 的一个拷贝
return;
}
for (选择 : 选择列表) {
if (不合法) continue; // 剪枝
做选择; // 路径.add(选择)
backtrack(路径, 新的选择列表);
撤销选择; // 路径.remove(选择) ← 回溯的精髓
}
}三个关键点：
- 撤销选择必须在递归返回后立刻执行，保证父层状态干净；
- 记录结果必须拷贝（如
new ArrayList<>(path)），否则后续的修改会污染已保存的结果； - 剪枝决定性能：提前排除不可能的分支（如
used[i]、排序后跳过重复、可行性上界判断）。
复杂度：回溯的时间通常是指数级（
O(n!)或O(2ⁿ)），因为它在枚举整个决策树；空间是决策树深度O(n)（不含结果存储）。
7. 如何用回溯解决「全排列」与「子集」？
答： 两题的差异只在"结束条件"与"下一层的起点"。
全排列（顺序相关，用 used 标记已选元素）：
import java.util.ArrayList;
import java.util.List;
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
backtrackPermute(nums, new boolean[nums.length], new ArrayList<>(), res);
return res;
}
private void backtrackPermute(int[] nums, boolean[] used, List<Integer> path,
List<List<Integer>> res) {
if (path.size() == nums.length) { // 结束条件：选满 n 个
res.add(new ArrayList<>(path)); // 必须拷贝！
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue; // 剪枝：用过的不能再选
used[i] = true;
path.add(nums[i]);
backtrackPermute(nums, used, path, res);
path.remove(path.size() - 1); // 撤销
used[i] = false;
}
}子集（顺序无关，用 start 避免重复组合）：
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
backtrackSubsets(nums, 0, new ArrayList<>(), res);
return res;
}
private void backtrackSubsets(int[] nums, int start, List<Integer> path,
List<List<Integer>> res) {
res.add(new ArrayList<>(path)); // 每个节点都是一个合法子集，先收集
for (int i = start; i < nums.length; i++) {
path.add(nums[i]);
backtrackSubsets(nums, i + 1, path, res); // 从 i+1 开始 → 元素不重复使用
path.remove(path.size() - 1);
}
}区分要点：排列要"所有元素都用到、顺序有别"，因此每层都从头遍历 +
used标记；组合/子集"只用后面的元素、顺序无关"，因此从start往后遍历。组合总和类题目在此基础上加"剪枝"（如排序后提前break）。
三、贪心
8. 什么是贪心算法？与动态规划的区别是什么？
答： 贪心在每一步都做当前看起来最优的选择，且不回溯，期望局部最优能导向全局最优。
贪心成立的两个前提（面试必须能说清）：
- 贪心选择性质：每一步的局部最优选择，一定能构成某个全局最优解；
- 最优子结构：问题的最优解包含其子问题的最优解。
贪心 vs 动态规划：
| 维度 | 贪心 | 动态规划 |
|---|---|---|
| 决策方式 | 每步取局部最优，不回头 | 考虑所有子问题，综合比较 |
| 是否回溯 | 永不回溯 | 通过状态转移"回溯"所有可能 |
| 复杂度 | 通常 O(n) 或 O(n log n) | 通常 O(n²) 或更高 |
| 正确性 | 需要证明，不总成立 | 只要状态与转移正确即成立 |
| 典型题 | 区间调度、跳跃游戏、分发饼干、霍夫曼编码 | 背包、LIS、编辑距离、零钱兑换 |
贪心失效的经典反例：硬币面值 {1, 3, 4}，凑 6 元。
- 贪心：先拿最大的
4，剩2→ 再拿1 + 1，共用 3 枚； - 最优：
3 + 3，只用 2 枚。
面试提醒：被问到"这题用贪心"时，面试官通常会追问"如何证明贪心选择性质"（常用交换论证：假设最优解不用贪心选择，通过替换构造出一个不更差的解，导出矛盾）。答不出证明就直接说"应该用 DP"，比硬撑贪心更安全。
四、动态规划
9. 什么是动态规划？解题四步套路是什么？
答： 动态规划（DP） 用于解决具有最优子结构与重叠子问题的问题：把问题拆成有重叠的子问题，缓存子问题的解避免重复计算。
与分治的区别：分治的子问题相互独立（不重叠），DP 的子问题重叠，因此 DP 必须"记表"。
解题四步套路（万能）：
- 定义状态：
dp[i]（或dp[i][j]）到底表示什么？——这一步最重要，定义错了后面全错； - 推导状态转移方程：
dp[i]与dp[i-1]、dp[i-2]… 的关系； - 确定初始条件与边界：
dp[0]、dp[1]是什么？空集/空串如何处理？ - 确定遍历顺序：确保计算
dp[i]时它依赖的状态已经算好（一维优化时顺序尤其关键）。
两种实现方式：
- 自顶向下 + 备忘录（记忆化搜索）：写递归 +
memo数组，思路自然、直接对应递归式； - 自底向上 + 递推表：写循环填表，无递归栈开销，便于做空间优化。
// 以"爬楼梯"为例：每次可走 1 或 2 阶，求走到第 n 阶的方法数
// 状态：dp[i] = 走到第 i 阶的方法数
// 转移：dp[i] = dp[i-1] + dp[i-2]（最后一步走 1 阶或 2 阶）
// 边界：dp[0] = 1, dp[1] = 1
public int climbStairs(int n) {
if (n <= 1) return 1;
int prev2 = 1, prev1 = 1; // 只保留前两个状态 → 空间 O(1)
for (int i = 2; i <= n; i++) {
int cur = prev1 + prev2;
prev2 = prev1;
prev1 = cur;
}
return prev1;
}空间优化（滚动数组）：若
dp[i]只依赖前几个状态，就可以用常数个变量或滚动数组把空间从O(n)降到O(1)。这是 DP 题的常见加分项。
10. 0-1 背包问题如何实现？（含一维滚动数组优化）
答： 0-1 背包：给定 n 个物品（重量 w[i]、价值 v[i]）和容量 C 的背包，每个物品只能选 0 或 1 次，求最大总价值。
二维定义：dp[i][j] = 考虑前 i 个物品、容量为 j 时的最大价值：
dp[i][j] = max(dp[i-1][j], // 不选第 i 个
dp[i-1][j - w[i]] + v[i]) // 选第 i 个（需 j >= w[i]）一维滚动数组优化（dp[j] 直接复用，内层必须倒序）：
public int knapsack01(int[] weights, int[] values, int capacity) {
int[] dp = new int[capacity + 1]; // dp[j] = 容量 j 时的最大价值
for (int i = 0; i < weights.length; i++) {
// 必须【倒序】遍历容量，保证 dp[j - w[i]] 用的是"上一轮"（i-1）的状态
for (int j = capacity; j >= weights[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
}
}
return dp[capacity];
}为什么必须倒序？（本题最核心的考点）
- 倒序时，
dp[j - w[i]]尚未被本轮更新，代表的是上一行dp[i-1][...]的值——这正符合"每个物品只用一次"；- 若写成正序，
dp[j - w[i]]已经是本轮（i）更新过的值，等于允许第i个物品被重复放入——那就变成了完全背包。一句话：0-1 背包倒序、完全背包正序，区别就是"能不能重复用"。
11. 完全背包与零钱兑换如何实现？
答： 完全背包：每个物品可无限次使用——只需把 0-1 背包的内层改成正序。
public int knapsackComplete(int[] weights, int[] values, int capacity) {
int[] dp = new int[capacity + 1];
for (int i = 0; i < weights.length; i++) {
for (int j = weights[i]; j <= capacity; j++) { // 正序 → 允许重复使用
dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
}
}
return dp[capacity];
}零钱兑换：给硬币面额（每种无限多）与目标金额，求最少硬币数，凑不出返回 -1。这是"完全背包求最小值"的变形。
import java.util.Arrays;
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1); // 用"不可能达到的较大值"表示无解
dp[0] = 0; // 凑出 0 元需要 0 枚
for (int coin : coins) {
for (int j = coin; j <= amount; j++) { // 完全背包，正序
dp[j] = Math.min(dp[j], dp[j - coin] + 1); // 取"硬币数最少"
}
}
return dp[amount] > amount ? -1 : dp[amount];
}背包问题的三个变体对照：
变体 内层遍历方向 求什么 0-1 背包 倒序 最大价值（每件 1 次） 完全背包 正序 最大价值（每件无限次） 零钱兑换 正序 最小数量 进阶考点：若问"凑出金额的方案数"，把
max/min换成累加即可（dp[j] += dp[j - coin]）；若要求组合数（112 与 211 视为同一种），必须外层遍历物品、内层遍历容量；若要求排列数（视为不同），则外层遍历容量、内层遍历物品——这个顺序差异是高频考点。
12. 最长递增子序列（LIS）如何实现？
答：
解法一：动态规划 O(n²)
import java.util.Arrays;
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length]; // dp[i] = 以 nums[i] 结尾的 LIS 长度
Arrays.fill(dp, 1); // 每个元素自身构成长度 1
int max = 1;
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
}
max = Math.max(max, dp[i]);
}
return max;
}解法二：贪心 + 二分 O(n log n)
维护 tails 数组：tails[k] 表示长度为 k+1 的递增子序列的最小结尾值。结尾越小，后续越容易接上更长的序列。
public int lengthOfLISFast(int[] nums) {
int[] tails = new int[nums.length];
int size = 0;
for (int num : nums) {
// 在 tails[0..size) 中二分找第一个 >= num 的位置
int left = 0, right = size;
while (left < right) {
int mid = left + (right - left) / 2;
if (tails[mid] < num) left = mid + 1;
else right = mid;
}
tails[left] = num; // 替换（贪心地让结尾更小）
if (left == size) size++; // 追加到末尾 → 长度 +1
}
return size;
}重要澄清：
tails数组本身不是 LIS，它只是"各长度的最小结尾值"这一辅助结构，其长度才等于 LIS 长度。若题目要求输出具体序列，需要用O(n²)的 DP 并记录前驱，或额外维护每个tails[k]对应的下标。
13. 最长公共子序列（LCS）与编辑距离如何实现？
答：
最长公共子序列（LCS）：dp[i][j] = a 前 i 个字符与 b 前 j 个字符的 LCS 长度。
public int longestCommonSubsequence(String a, String b) {
int m = a.length(), n = b.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1; // 字符相同 → 各退一步 +1
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // 舍弃 a 的或 b 的一个字符
}
}
}
return dp[m][n];
}空间优化为一维（dp[i][j] 只依赖上一行与左邻，需额外变量保存"左上角"）：
public int lcs1D(String a, String b) {
int n = b.length();
int[] dp = new int[n + 1];
for (int i = 1; i <= a.length(); i++) {
int prev = 0; // 保存 dp[i-1][j-1]（已被覆盖的左上角）
for (int j = 1; j <= n; j++) {
int tmp = dp[j]; // 覆盖前的 dp[j] 即 dp[i-1][j]
if (a.charAt(i - 1) == b.charAt(j - 1)) dp[j] = prev + 1;
else dp[j] = Math.max(dp[j], dp[j - 1]);
prev = tmp; // 供下一列当"左上角"
}
}
return dp[n];
}编辑距离：把 a 变成 b 所需的最少操作数（插入 / 删除 / 替换各算一次）。
public int minDistance(String a, String b) {
int m = a.length(), n = b.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) dp[i][0] = i; // a 的前 i 个 → 空串：需 i 次删除
for (int j = 0; j <= n; j++) dp[0][j] = j; // 空串 → b 的前 j 个：需 j 次插入
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1]; // 字符相同，无需操作
} else {
dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], // 替换
Math.min(dp[i - 1][j], // 删除 a[i-1]
dp[i][j - 1])); // 插入 b[j-1]
}
}
}
return dp[m][n];
}两个矩阵 DP 的通用套路：行是
a、列是b，dp[i][j]表示"前缀a[0..i-1]与前缀b[0..j-1]"，多开一行一列处理空串。字符相同时"各退一步"，不同时按题意取max（LCS）或min + 1（编辑距离）。复杂度：时间
O(m × n)，二维空间O(m × n)，可优化为一维O(n)。
五、位运算
14. 常用位运算技巧有哪些？
答： 位运算的常数极小、常能带来"降维"效果，是高频加分项。
| 技巧 | 表达式 | 用途 |
|---|---|---|
| 判断奇偶 | n & 1 | 比 % 2 快；结果为 1 是奇数 |
| 除以 2 | n >> 1 | 右移代替除法（注意负数） |
| 消去最低位的 1 | n & (n - 1) | 统计二进制中 1 的个数；判断是否为 2 的幂 |
| 取最低位的 1 | n & -n | 树状数组（lowbit）、求"只出现一次"的位 |
| 判断第 k 位 | (n >> k) & 1 | 位图标记 |
| 置位 / 清位 | n | (1 << k) / n & ~(1 << k) | 状态压缩、位图 |
| 交换两数 | a ^= b; b ^= a; a ^= b; | 不用临时变量（可读性差，慎用） |
实战一：判断 2 的幂
public boolean isPowerOfTwo(int n) {
// 2 的幂的二进制只有 1 个 1，消去后应为 0；n > 0 排除负数和 0
return n > 0 && (n & (n - 1)) == 0;
}实战二：统计二进制中 1 的个数
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
n &= (n - 1); // 每次消去一个 1，循环次数 = 1 的个数（比逐位判断更优）
count++;
}
return count;
}实战三：找出只出现一次的数字（其余都出现两次）
public int singleNumber(int[] nums) {
int res = 0;
for (int num : nums) res ^= num; // 异或满足 a^a=0, a^0=a，成对的数自动抵消
return res;
}位运算的三大应用方向：
- 状态压缩 DP：用整数的每一位表示一个"选/不选"，如旅行商问题、集合覆盖；
- 位图（BitMap）：用 1 个 bit 表示一个布尔状态，比
boolean[]省 8 倍空间，适合海量数据的去重与存在性判断（如 40 亿个数找是否存在）；- 异或的巧妙用法：不借助临时变量交换、找唯一出现元素、找缺失数字（
1..n与数组全体异或）。