嘿，你好啊！我是 Agnes。
我知道你现在可能正盯着屏幕发呆，或者刚刚被一道 “两数之和” 卡了半小时，心里有点慌。别急，咱们坐下来，泡杯咖啡，像朋友聊天一样把这事儿捋清楚。
很多 Java 同学有个误区，觉得背八股文就能进大厂。其实吧，算法题才是那道真正的”拦路虎”。尤其是现在卷成这样，面试官随随便便出一题中等难度的动态规划，就能看出你逻辑清不清晰。
但这篇教程不是让你死记硬背代码的，我是来帮你建立肌肉记忆的。咱们从最基础的排序开始，一路杀到动态规划，每道题我都会告诉你：为什么要这么做？坑在哪里？Java 里怎么写最优雅？
准备好了吗？咱们开始。
第一部分：为什么排序是基石？
你可能会问：“面试又不会让我写快排，我为什么要刷排序？”
好问题。但你要知道，所有高级算法的底层，都是排序或者基于排序的优化。比如归并排序的“分治思想”是动态规划的前置知识，堆排序的思想是解决“Top K”问题的核心，而快速排序的“双指针”技巧在解决数组问题时无处不在。
1.1 快速排序（Quick Sort）：必须手写的经典
在 Java 面试中，手写快速排序是基础中的基础。它考察你对递归、边界条件和原地交换的理解。
核心逻辑： 找一个基准值（pivot），把比它小的放左边，比它大的放右边，然后对左右两边递归重复这个过程。
Java 实战代码：
public class QuickSort {
public static void sort(int[] arr, int low, int high) {
if (low < high) {
// 获取分区点
int pivotIndex = partition(arr, low, high);
// 递归排序左子数组
sort(arr, low, pivotIndex - 1);
// 递归排序右子数组
sort(arr, pivotIndex + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
// 选择最后一个元素作为基准
int pivot = arr[high];
// i 是小于基准区的边界索引
int i = low - 1;
for (int j = low; j < high; j++) {
// 如果当前元素小于等于基准
if (arr[j] <= pivot) {
i++;
// 交换 arr[i] 和 arr[j]
swap(arr, i, j);
}
}
// 将基准元素放到正确的位置
swap(arr, i + 1, high);
return i + 1;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 测试
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
sort(arr, 0, arr.length - 1);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
👨🏫 老农讲解时间：
你看那个 i 和 j，别搞混了。
j是探路的，它到处看，“嗯，这个比基准小，好，挪到左边去”。i是守门的，它守着“小于基准区”的最后一道防线。- 最后一步
swap(arr, i + 1, high)特别关键，很多人写这里会把基准值丢进去。
面试坑点： 如果数组已经有序，快排会退化到 O(n²)。面试官如果追问优化，你可以说：“随机选择基准值”或者“三数取中法”。
1.2 归并排序（Merge Sort）：分治思想的祖师爷
归并排序是稳定排序，而且它的“分治”策略是理解更复杂算法的钥匙。
核心逻辑：
- 分：把数组从中间切开，一直切到只剩一个元素。
- 治：把两个有序的数组合并成一个有序数组。
Java 实战代码：
public class MergeSort {
public static void sort(int[] arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2; // 防止溢出
sort(arr, left, mid); // 排序左半边
sort(arr, mid + 1, right); // 排序右半边
merge(arr, left, mid, right); // 合并
}
}
private static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
// 创建临时数组
int[] L = new int[n1];
int[] R = new int[n2];
// 拷贝数据
System.arraycopy(arr, left, L, 0, n1);
System.arraycopy(arr, mid + 1, R, 0, n2);
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k++] = L[i++];
} else {
arr[k++] = R[j++];
}
}
// 拷贝剩余元素
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
}
👨🏫 老农讲解时间：
注意看 mid = left + (right - left) / 2。为什么要这么写？直接写 (left + right) / 2 在 left 和 right 很大的时候会整数溢出，变成负数，直接崩掉。这是细节，面试官很喜欢问。
归并排序的空间复杂度是 O(n)，因为它需要临时数组。如果面试官问“如何原地归并”，你可以诚实说：“那非常复杂且效率低，通常不这么做”，然后展示你对空间换时间的理解。
第二部分：字符串与数组——双指针的艺术
搞定了排序，咱们看看最常用的场景：双指针。
这道题：“三数之和” (LeetCode 15)
给你一个整数数组
nums，判断是否存在三元组[nums[i], nums[j], nums[k]]满足i != j、i != k且j != k，同时还满足nums[i] + nums[j] + nums[k] == 0。
很多新手会用三层循环暴力解，O(n³)，面试官直接摇头。我们要用排序 + 双指针，降到 O(n²)。
Java 实战代码：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class ThreeSum {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums); // 关键第一步：排序
for (int i = 0; i < nums.length - 2; i++) {
// 去重：如果当前数字和前一个一样，跳过，避免重复三元组
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum < 0) {
left++; // 太小了，左指针右移，增大总和
} else if (sum > 0) {
right--; // 太大了，右指针左移，减小总和
} else {
// 找到答案！
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
// 去重：左指针和右指针都要跳过重复元素
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
}
}
}
return result;
}
}
👨🏫 老农讲解时间：
这道题的精髓在去重。
- 外层循环去重：
if (i > 0 && nums[i] == nums[i - 1]) continue; - 内层找到解后，左右指针都要去重。
如果你不做去重，结果里会出现 [[-1, -1, 2], [-1, -1, 2]] 这样的重复项，面试直接挂。
你可以这样教小朋友理解：想象你有三根不同长度的木棍，要想拼成总长度为零（当然木棍不能为零，这里是比喻数值关系），你得先把木棍按长短排好队，然后固定第一根，用两根手指在剩下的队伍里找另外两根。
第三部分：链表——指针的华尔兹
链表题是 Java 面试的必考题，因为指针操作最能考察你的逻辑严密性。
经典题：“反转链表” (LeetCode 206)
给你单链表的头节点
head，请你反转链表，并返回反转后的链表。
Java 实战代码（迭代法）：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next; // 暂存下一个节点
curr.next = prev; // 反转指针
prev = curr; // prev 向前移动
curr = nextTemp; // curr 向前移动
}
return prev; // prev 成为新的头节点
}
}
👨🏫 老农讲解时间：
画个图！一定要画图！
prev初始是null，因为反转后，原来的头节点会变成尾节点，它的 next 应该指向 null。curr从头开始走。- 最关键的一步：
nextTemp = curr.next。如果你直接写curr.next = prev，那下一个节点就丢了！所以必须先“抓住”下一个节点。
递归写法（进阶）：
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
递归的理解稍微难一点：它先把后面的全反转了，然后让 head.next 的 next 指回 head，再把 head 的 next 置空。就像排队倒着走，后面的人先回头，前面的人才回头。
第四部分：动态规划——从懵逼到真香
好了，重头戏来了。动态规划（DP）是面试的“杀手锏”，也是很多程序员的噩梦。
但我告诉你，DP 其实就一件事：把大问题拆成小问题，并且把小问题的答案存起来，别重复算。
4.1 斐波那契数列：入门必刷
题目： 写一个函数，输入 n，求斐波那契数列的第 n 项。
错误示范（纯递归）：
public int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
问题： 指数级时间复杂度 O(2^n)。算到 n=50 你就等到天荒地老。因为 fib(5) 会被算很多次。
正确姿势（记忆化搜索/DP）：
public int fib(int n) {
if (n <= 1) return n;
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
👨🏫 老农讲解时间：
你看，我们开一个数组 dp，dp[i] 就代表“第 i 个斐波那契数”。
- 状态转移方程：
dp[i] = dp[i-1] + dp[i-2] - 这一步就是把“大问题”拆成了“前两个小问题”的答案之和。
- 空间复杂度可以优化到 O(1)，因为你只需要前两个数，不需要存整个数组。
public int fibOptimized(int n) {
if (n <= 1) return n;
int prev2 = 0;
int prev1 = 1;
int curr = 0;
for (int i = 2; i <= n; i++) {
curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return curr;
}
4.2 爬楼梯：DP 的真实应用场景
题目： 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。有多少种不同的方法可以爬到楼顶？
分析：
- 爬到第 1 阶：1 种方法 (1)
- 爬到第 2 阶：2 种方法 (1+1, 2)
- 爬到第 3 阶：3 种方法 (1+1+1, 1+2, 2+1)
- 爬到第 n 阶：要么从 n-1 阶爬 1 步上来，要么从 n-2 阶爬 2 步上来。
所以：dp[n] = dp[n-1] + dp[n-2]
这不就是斐波那契吗？ 对！所以 DP 不是魔法，它只是换个包装的数学题。
public int climbStairs(int n) {
if (n <= 2) return n;
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
4.3 最小路径和：二维 DP 的入门
题目： 给定一个包含非负整数的 m x n 网格 grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
分析： 只能向右或向下走。
- 到达
(i, j)的最小路径和 =min(从上面来的, 从左面来的) + 当前格子的值 - 边界条件：第一行只能从左边来，第一列只能从上面来。
Java 实战代码：
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
// dp[i][j] 表示从 (0,0) 到 (i,j) 的最小路径和
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
// 初始化第一列
for (int i = 1; i < m; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
// 初始化第一行
for (int j = 1; j < n; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
// 填充其余部分
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[m - 1][n - 1];
}
👨🏫 老农讲解时间：
二维 DP 看起来吓人，其实和二维数组遍历一模一样。
- 找状态：
dp[i][j]是什么？是从起点到当前位置的最优解。 - 找转移方程：
min(上, 左) + 当前值。 - 找边界：第一行和第一列没有“上”或“左”，要单独处理。
记住，DP 三步走：
- 定义
dp数组的含义。 - 写出状态转移方程。
- 确定初始值和边界情况。