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

先写暴力解法再做优化

先写暴力解法再做优化

面对一道新题时,先写清晰的暴力解法,可以快速确认输入、输出和边界规则,再从运行过程中的重复工作寻找优化点。本课以“两数之和”为主示例,演示如何建立基线、引入哈希索引,并用对拍验证两种实现的语义一致性。

学习目标

  • 用暴力解法建立可验证的正确性基线
  • 从重复扫描中识别可优化的关键操作
  • 使用随机对拍检查优化前后的结果是否等价

建立基线并定位重复工作

两数之和要求在数组中找到两个不同下标,使对应元素之和等于目标值。最直接的方案是枚举所有满足 i < j 的下标对:实现容易检查,也天然避免同一元素被使用两次,但时间复杂度为 O(n2)O(n^2)。

暴力方案的价值不只是“能通过小数据”。它还明确了无解时返回什么、重复值如何处理、多个答案是否允许任取一个。优化版本必须遵守同一份契约,否则性能再高也不是等价实现。

双重循环的重复工作,是每处理一个元素都重新扫描其他位置寻找补数。处理当前值 value 时,真正需要回答的问题是:此前是否出现过 target - value。

用哈希表保存“已访问数值到下标”的映射后,补数查询平均可降为 O(1)O(1),整体平均时间复杂度为 O(n)O(n),额外空间复杂度为 O(n)O(n)。查询必须发生在写入当前元素之前,否则当 target == 2 * value 时,当前元素可能与自身配对。

暴力扫描与哈希索引的优化路径

主示例:实现并对拍

下面的 Java 17 示例保留暴力版和哈希版。固定样例用于观察操作次数,随后用固定随机种子生成 500 组小输入,对比两版是否都能找到合法答案。由于题目允许多个答案,对拍比较的是“是否有解且返回下标有效”,而不是强制下标完全相同。

java
import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class BruteForceOptimizationDemo {
    private record Pair(int first, int second, int operations) {
        boolean found() {
            return first >= 0;
        }
    }

    public static void main(String[] args) {
        int[] values = {2, 7, 11, 15};
        Pair bruteResult = bruteForce(values, 9);
        Pair fastResult = hashLookup(values, 9);

        System.out.println("暴力结果: " + format(bruteResult));
        System.out.println("暴力比较次数: " + bruteResult.operations());
        System.out.println("优化结果: " + format(fastResult));
        System.out.println("哈希查询次数: " + fastResult.operations());

        Random random = new Random(20260801L);
        for (int round = 1; round <= 500; round++) {
            int[] sample = randomArray(random, 8, -10, 10);
            int target = random.nextInt(21) - 10;
            Pair expected = bruteForce(sample, target);
            Pair actual = hashLookup(sample, target);
            if (!semanticallyEqual(sample, target, expected, actual)) {
                throw new AssertionError("第 " + round + " 组对拍失败");
            }
        }
        System.out.println("对拍通过: 500 组");
    }

    private static Pair bruteForce(int[] values, int target) {
        int operations = 0;
        for (int i = 0; i < values.length; i++) {
            for (int j = i + 1; j < values.length; j++) {
                operations++;
                if ((long) values[i] + values[j] == target) {
                    return new Pair(i, j, operations);
                }
            }
        }
        return new Pair(-1, -1, operations);
    }

    private static Pair hashLookup(int[] values, int target) {
        Map<Integer, Integer> firstIndex = new HashMap<>();
        int operations = 0;
        for (int i = 0; i < values.length; i++) {
            operations++;
            long complement = (long) target - values[i];
            Integer previous = complement >= Integer.MIN_VALUE
                    && complement <= Integer.MAX_VALUE
                    ? firstIndex.get((int) complement)
                    : null;
            if (previous != null) {
                return new Pair(previous, i, operations);
            }
            // 先查询后写入,并用 long 计算补数以避免 int 溢出。
            firstIndex.putIfAbsent(values[i], i);
        }
        return new Pair(-1, -1, operations);
    }

    private static boolean semanticallyEqual(
            int[] values, int target, Pair expected, Pair actual) {
        if (expected.found() != actual.found()) {
            return false;
        }
        return !actual.found()
                || actual.first() != actual.second()
                && (long) values[actual.first()]
                + values[actual.second()] == target;
    }

    private static int[] randomArray(
            Random random, int maxLength, int minValue, int maxValue) {
        int[] values = new int[random.nextInt(maxLength + 1)];
        for (int i = 0; i < values.length; i++) {
            values[i] = random.nextInt(maxValue - minValue + 1) + minValue;
        }
        return values;
    }

    private static String format(Pair pair) {
        return pair.found() ? "[" + pair.first() + ", " + pair.second() + "]" : "无解";
    }
}

将代码保存为 BruteForceOptimizationDemo.java,然后编译运行:

bash
javac BruteForceOptimizationDemo.java
java BruteForceOptimizationDemo

预期输出:

text
暴力结果: [0, 1]
暴力比较次数: 1
优化结果: [0, 1]
哈希查询次数: 2
对拍通过: 500 组

优化时的检查重点

先确认重复工作是否真实存在,再选择索引、缓存、前缀和或剪枝等工具。不要为了使用高级数据结构而改变问题语义。

对拍时应覆盖空数组、单元素、重复值、负数和无解输入。发现差异后,保留最小失败用例作为回归测试;对于多解问题,应比较题目规定的语义,而不是机械比较两个返回对象是否完全相同。

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

目录与阅读设置

阅读设置

17

记录一个想法

先写暴力解法再做优化

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

登录哪都通