数据结构与算法 / 系统课时
识别常见算法模式
识别常见算法模式
许多业务题目的表述不同,底层结构却相似。识别算法模式可以快速缩小方案范围,但关键词不能替代证明;本课将总结常见信号,并以有序数组配对为主示例,演示如何验证双指针的移动依据。
学习目标
- 根据数据结构与目标识别常见算法模式
- 判断模式依赖的有序性、连续性或单调性
- 用可排除性验证双指针移动是否正确
从问题特征寻找候选模式
常见模式及其成立条件如下:
| 问题特征 | 候选模式 | 必须验证的前提 |
|---|---|---|
| 有序序列中的配对或两端收缩 | 双指针 | 指针移动能排除一批候选 |
| 连续区间且状态可增量维护 | 滑动窗口 | 扩张与收缩具有可预测变化 |
| 有序数据或单调判定 | 二分查找 | 判定结果在边界两侧单调 |
| 节点、连接、依赖或状态迁移 | DFS、BFS、拓扑排序 | 边的含义和访问状态明确 |
| 重叠子问题与阶段转移 | 动态规划 | 状态能概括必要历史 |

一个问题可能组合多个模式。例如先排序再双指针,或使用二分查找外层答案、内部用贪心算法验证。组合前应分别证明每一层模式的前提。
主示例:有序数组两数之和
给定升序数组和目标值,寻找两个数使其和等于目标值。左指针指向最小值,右指针指向最大值:
- 当前和小于目标值时,右端不变而继续减小左值只会让和更小,因此可以安全右移左指针。
- 当前和大于目标值时,左端不变而继续增大右值只会让和更大,因此可以安全左移右指针。
这就是双指针成立的核心:每次移动都能证明被跳过的候选不可能成为答案。若数组无序,这个证明不成立,应先排序或改用哈希表。
完整可运行示例
java
import java.util.Arrays;
public class PatternRecognitionDemo {
public static void main(String[] args) {
int[] values = {1, 2, 4, 7, 11};
int target = 9;
int[] answer = twoSum(values, target);
System.out.println("数组: " + Arrays.toString(values));
System.out.println("目标值: " + target);
System.out.println("结果下标: " + Arrays.toString(answer));
if (answer.length == 2) {
System.out.println(
"对应元素: " + values[answer[0]] + " + " + values[answer[1]]
);
}
}
private static int[] twoSum(int[] values, int target) {
int left = 0;
int right = values.length - 1;
while (left < right) {
int sum = values[left] + values[right];
if (sum == target) {
return new int[]{left, right};
}
// 升序性保证移动后不会漏掉可行解
if (sum < target) {
left++;
} else {
right--;
}
}
return new int[0];
}
}将代码保存为 PatternRecognitionDemo.java,然后执行:
bash
javac PatternRecognitionDemo.java
java PatternRecognitionDemo预期输出:
text
数组: [1, 2, 4, 7, 11]
目标值: 9
结果下标: [1, 3]
对应元素: 2 + 7程序返回下标 [1, 3]。每次移动都依赖数组升序这一前提,因此时间复杂度为 O(n),额外空间为 O(1)。
易混淆的模式边界
滑动窗口通常要求目标是连续区间,并且窗口加入或移除元素后,状态能增量更新。对于“正数数组中和至少为目标值的最短子数组”,窗口和具有单调变化;加入负数后,简单收缩规则可能失效。
二分查找不只用于查找元素,也可用于“二分答案”,但必须先证明判定函数单调。图问题则常隐藏在课程依赖、任务先后关系、状态跳转或最短步数中;无权最短路径通常优先考虑 BFS。
动态规划的关键不是题目出现“最大”或“最少”,而是存在重复子问题,且有限状态能够概括后续决策需要的历史信息。
按自己的节奏,确认真正理解。