LeetCode刷题笔记：我用Java刷完HOT100，总结了这50个核心解题模板-洪萨配资

LeetCode刷题进阶指南：Java版50个高频算法模板精析

刷LeetCode时，你是否经常遇到似曾相识的题目却无从下手？或是看懂了题解却难以在面试中快速实现？本文将从实战角度出发，系统梳理50个高频算法模板，帮助Java开发者建立解题思维框架。不同于简单的题解汇总，我们将深入剖析每种模式的适用场景、变种考法及实现细节，让你真正掌握"以不变应万变"的解题能力。

1. 双指针模板全解析

双指针是解决数组/链表问题的利器，其核心在于通过两个指针的协同移动降低时间复杂度。根据指针移动方向，可分为同向指针、对向指针和快慢指针三种经典模式。

1.1 同向指针模板

适用于需要维护动态窗口的场景，如子数组/子串问题。模板代码如下：

public int slidingWindowTemplate(int[] nums, int k) { int left = 0, result = 0; for (int right = 0; right < nums.length; right++) { // 更新窗口状态 while (/* 不满足条件时 */) { // 移动左指针并调整状态 left++; } // 更新结果 result = Math.max(result, right - left + 1); } return result; }

典型应用场景：

无重复字符的最长子串（LeetCode 3）
最小覆盖子串（LeetCode 76）
长度最小的子数组（LeetCode 209）

易错点提醒：

窗口收缩条件判断要准确，避免漏解或重复计算。特别注意边界条件如空输入或单元素情况。

1.2 对向指针模板

常用于有序数组的两数之和、三数之和等问题。基础实现：

public int twoPointers(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left < right) { int sum = nums[left] + nums[right]; if (sum == target) { return /* 结果处理 */; } else if (sum < target) { left++; } else { right--; } } return /* 默认结果 */; }

变种考法：

三数之和（LeetCode 15）需结合排序+双指针
盛最多水的容器（LeetCode 11）需计算面积最大值
接雨水（LeetCode 42）需维护左右最大值

1.3 快慢指针模板

链表问题的经典解法，典型应用包括环检测和中间节点查找：

public boolean hasCycle(ListNode head) { ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) return true; } return false; }

进阶应用：

寻找环入口（LeetCode 142）
链表中点（LeetCode 876）
重排链表（LeetCode 143）

2. 深度优先搜索(DFS)模板精讲

DFS是解决树形结构和排列组合问题的核心方法。根据处理顺序可分为前序、中序、后序三种遍历方式，每种都有其特定的应用场景。

2.1 二叉树遍历模板

递归实现简洁明了，但需注意栈溢出风险：

// 前序遍历 void preorder(TreeNode root) { if (root == null) return; System.out.println(root.val); // 处理当前节点 preorder(root.left); preorder(root.right); } // 中序遍历 void inorder(TreeNode root) { if (root == null) return; inorder(root.left); System.out.println(root.val); // 处理当前节点 inorder(root.right); }

迭代实现通常更高效，使用显式栈模拟递归过程：

public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); TreeNode curr = root; while (curr != null || !stack.isEmpty()) { while (curr != null) { stack.push(curr); curr = curr.left; } curr = stack.pop(); res.add(curr.val); curr = curr.right; } return res; }

2.2 回溯算法模板

解决组合、排列、子集等问题的通用框架：

public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> res = new ArrayList<>(); backtrack(res, new ArrayList<>(), nums, 0); return res; } private void backtrack(List<List<Integer>> res, List<Integer> temp, int[] nums, int start) { res.add(new ArrayList<>(temp)); // 添加当前组合 for (int i = start; i < nums.length; i++) { temp.add(nums[i]); // 选择当前元素 backtrack(res, temp, nums, i + 1); // 递归 temp.remove(temp.size() - 1); // 撤销选择 } }

关键点：

路径记录：保存已做出的选择
选择列表：当前可做的选择
结束条件：达到决策树底层时的处理

常见变种：

全排列（LeetCode 46）
组合总和（LeetCode 39）
括号生成（LeetCode 22）

3. 动态规划(DP)框架详解

动态规划通过将问题分解为子问题来优化求解过程。掌握状态定义、转移方程和初始化是解题关键。

3.1 线性DP模板

一维DP问题的典型结构：

public int linearDP(int[] nums) { int[] dp = new int[nums.length]; // 初始化 dp[0] = nums[0]; for (int i = 1; i < nums.length; i++) { // 状态转移 dp[i] = Math.max(dp[i-1] + nums[i], nums[i]); } // 结果处理 return Arrays.stream(dp).max().getAsInt(); }

经典问题：

最大子数组和（LeetCode 53）
打家劫舍（LeetCode 198）
爬楼梯（LeetCode 70）

3.2 二维DP模板

处理矩阵路径等问题的通用模式：

public int twoDimensionalDP(int[][] grid) { int m = grid.length, n = grid[0].length; int[][] dp = new int[m][n]; // 初始化第一行和第一列 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]; }

应用场景：

最小路径和（LeetCode 64）
不同路径（LeetCode 62）
编辑距离（LeetCode 72）

3.3 状态压缩DP技巧

当状态只与前一状态相关时，可优化空间复杂度：

public int rob(int[] nums) { int prev = 0, curr = 0; for (int num : nums) { int temp = curr; curr = Math.max(prev + num, curr); prev = temp; } return curr; }

优化要点：

识别可以压缩的状态维度
合理安排状态更新顺序
注意边界条件处理

4. 数据结构应用模板

合理的数据结构选择能极大提升算法效率。以下是四种高频数据结构的典型应用模式。

4.1 单调栈模板

解决"下一个更大元素"类问题的利器：

public int[] nextGreaterElement(int[] nums) { int[] res = new int[nums.length]; Stack<Integer> stack = new Stack<>(); for (int i = nums.length - 1; i >= 0; i--) { while (!stack.isEmpty() && stack.peek() <= nums[i]) { stack.pop(); } res[i] = stack.isEmpty() ? -1 : stack.peek(); stack.push(nums[i]); } return res; }

典型问题：

每日温度（LeetCode 739）
柱状图中最大矩形（LeetCode 84）
下一个更大元素I（LeetCode 496）

4.2 堆(优先队列)模板

处理TopK问题的标准解法：

public int[] topKFrequent(int[] nums, int k) { Map<Integer, Integer> frequency = new HashMap<>(); for (int num : nums) { frequency.put(num, frequency.getOrDefault(num, 0) + 1); } PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> frequency.get(a) - frequency.get(b)); for (int num : frequency.keySet()) { heap.offer(num); if (heap.size() > k) heap.poll(); } int[] res = new int[k]; for (int i = k - 1; i >= 0; i--) { res[i] = heap.poll(); } return res; }

应用场景：

前K个高频元素（LeetCode 347）
合并K个升序链表（LeetCode 23）
数据流的中位数（LeetCode 295）

4.3 并查集模板

处理连通性问题的优雅方案：

class UnionFind { private int[] parent; public UnionFind(int size) { parent = new int[size]; for (int i = 0; i < size; i++) parent[i] = i; } public int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); return parent[x]; } public void union(int x, int y) { parent[find(x)] = find(y); } }

典型应用：

岛屿数量（LeetCode 200）
朋友圈（LeetCode 547）
冗余连接（LeetCode 684）

4.4 LRU缓存实现模板

结合哈希表和双向链表的经典设计：

class LRUCache { class DLinkedNode { int key, value; DLinkedNode prev, next; } private void addNode(DLinkedNode node) { node.prev = head; node.next = head.next; head.next.prev = node; head.next = node; } private void removeNode(DLinkedNode node) { node.prev.next = node.next; node.next.prev = node.prev; } private void moveToHead(DLinkedNode node) { removeNode(node); addNode(node); } private DLinkedNode popTail() { DLinkedNode res = tail.prev; removeNode(res); return res; } // 其余实现细节参考LeetCode 146 }

设计要点：