常用算法技巧总结
2025/6/4大约 4 分钟
一、双指针（Two Pointers）
定义
使用两个指针变量在数组或链表中按特定规则同时遍历，常用于解决有序数组、字符串或链表的问题。
使用场景
- 查找有序数组中两个数的和（对撞指针）
- 删除重复元素、快慢指针问题
- 合并有序数组或链表
实现方式（Java）
public boolean 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 true;
else if (sum < target) left++;
else right--;
}
return false;
}二、滑动窗口（Sliding Window）
定义
维护一个满足特定条件的窗口区间，窗口可以在数组或字符串上左右滑动，通常用于子串或子数组问题。
使用场景
- 最长无重复子串
- 最小覆盖子串
- 固定/变长子数组和问题
实现方式（Java）
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> map = new HashMap<>();
int left = 0, res = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (map.containsKey(c)) {
left = Math.max(left, map.get(c) + 1);
}
map.put(c, right);
res = Math.max(res, right - left + 1);
}
return res;
}三、动态规划（Dynamic Programming）
定义
将复杂问题分解为重复的子问题，通过保存子问题的解避免重复计算，从而降低时间复杂度。
使用场景
- 背包问题
- 最长公共子序列、最长上升子序列
- 爬楼梯、斐波那契数列
实现方式（Java）
public int fib(int n) {
if (n <= 1) return n;
int[] dp = new int[n + 1];
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}四、深度优先搜索（DFS）
定义
递归或使用栈不断深入搜索路径或解空间，直到不能深入为止。
使用场景
- 图/树遍历
- 岛屿数量、连通块计数
- 回溯问题（如排列组合）
实现方式（Java）
public void dfs(int node, boolean[] visited, List<List<Integer>> graph) {
if (visited[node]) return;
visited[node] = true;
for (int neighbor : graph.get(node)) {
dfs(neighbor, visited, graph);
}
}五、广度优先搜索（BFS）
定义
按层遍历图或树的节点，通常使用队列实现，用于查找最短路径等问题。
使用场景
- 图的最短路径（无权图）
- 二叉树层序遍历
- 多源最短路径、迷宫问题
实现方式（Java）
public void bfs(int start, List<List<Integer>> graph) {
boolean[] visited = new boolean[graph.size()];
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
visited[start] = true;
while (!queue.isEmpty()) {
int node = queue.poll();
for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.offer(neighbor);
}
}
}
}六、前缀和与差分
定义
通过构建前缀和数组或差分数组，实现快速区间查询或更新。
使用场景
- 子数组和查询
- 差分用于高效区间修改
实现方式（Java）
int[] nums = {1, 2, 3, 4};
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]说明：
前缀和数组 prefix 从索引 1 开始是为了让 prefix[i+1] 表示原数组中下标 0 到 i（即 nums[0..i]）这段的和。
我们设定 prefix[0] = 0，表示空区间的和为 0。这样做的目的是：
- 保证所有前缀和都可以统一使用差值公式计算；
- 使用公式
prefix[j + 1] - prefix[i]快速计算区间[i, j]的和，无需额外判断边界。
这是一种简洁且统一的实现方式，避免在使用前缀和时对起始位置特判处理。
七、二分查找（Binary Search）
定义
在有序数组中反复折半查找目标值或边界。
使用场景
- 查找有序数组中的目标
- 查找分界点、最大最小值
实现方式（Java）
public int binarySearch(int[] nums, int 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;
}
return -1;
}八、并查集（Union-Find）
定义
一种用于处理集合合并与查询的数据结构，支持查找集合代表元和集合合并。
使用场景
- 图的连通性判断
- 冗余连接检测
- Kruskal 最小生成树
实现方式（Java）
class UnionFind {
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) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
parent[rootY] = rootX;
}
}
}九、单调栈 / 单调队列
定义
栈（或队列）中元素保持单调性，用于快速查找前/后一个更大或更小的元素。
使用场景
- 下一个更大元素
- 滑动窗口最大值
- 柱状图最大矩形面积
实现方式（Java）
public int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] res = new int[n];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = n - 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;
}