数据结构与算法 / 系统课时

识别常见算法模式

识别常见算法模式

许多业务题目的表述不同,底层结构却相似。识别算法模式可以快速缩小方案范围,但关键词不能替代证明;本课将总结常见信号,并以有序数组配对为主示例,演示如何验证双指针的移动依据。

学习目标

  • 根据数据结构与目标识别常见算法模式
  • 判断模式依赖的有序性、连续性或单调性
  • 用可排除性验证双指针移动是否正确

从问题特征寻找候选模式

常见模式及其成立条件如下:

问题特征 候选模式 必须验证的前提
有序序列中的配对或两端收缩 双指针 指针移动能排除一批候选
连续区间且状态可增量维护 滑动窗口 扩张与收缩具有可预测变化
有序数据或单调判定 二分查找 判定结果在边界两侧单调
节点、连接、依赖或状态迁移 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。

动态规划的关键不是题目出现“最大”或“最少”,而是存在重复子问题,且有限状态能够概括后续决策需要的历史信息。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

识别常见算法模式

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通