数据结构与算法 / 系统课时
先写暴力解法再做优化
先写暴力解法再做优化
面对一道新题时,先写清晰的暴力解法,可以快速确认输入、输出和边界规则,再从运行过程中的重复工作寻找优化点。本课以“两数之和”为主示例,演示如何建立基线、引入哈希索引,并用对拍验证两种实现的语义一致性。
学习目标
- 用暴力解法建立可验证的正确性基线
- 从重复扫描中识别可优化的关键操作
- 使用随机对拍检查优化前后的结果是否等价
建立基线并定位重复工作
两数之和要求在数组中找到两个不同下标,使对应元素之和等于目标值。最直接的方案是枚举所有满足 i < j 的下标对:实现容易检查,也天然避免同一元素被使用两次,但时间复杂度为 。
暴力方案的价值不只是“能通过小数据”。它还明确了无解时返回什么、重复值如何处理、多个答案是否允许任取一个。优化版本必须遵守同一份契约,否则性能再高也不是等价实现。
双重循环的重复工作,是每处理一个元素都重新扫描其他位置寻找补数。处理当前值 value 时,真正需要回答的问题是:此前是否出现过 target - value。
用哈希表保存“已访问数值到下标”的映射后,补数查询平均可降为 ,整体平均时间复杂度为 ,额外空间复杂度为 。查询必须发生在写入当前元素之前,否则当 target == 2 * value 时,当前元素可能与自身配对。

主示例:实现并对拍
下面的 Java 17 示例保留暴力版和哈希版。固定样例用于观察操作次数,随后用固定随机种子生成 500 组小输入,对比两版是否都能找到合法答案。由于题目允许多个答案,对拍比较的是“是否有解且返回下标有效”,而不是强制下标完全相同。
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,然后编译运行:
javac BruteForceOptimizationDemo.java
java BruteForceOptimizationDemo预期输出:
暴力结果: [0, 1]
暴力比较次数: 1
优化结果: [0, 1]
哈希查询次数: 2
对拍通过: 500 组优化时的检查重点
先确认重复工作是否真实存在,再选择索引、缓存、前缀和或剪枝等工具。不要为了使用高级数据结构而改变问题语义。
对拍时应覆盖空数组、单元素、重复值、负数和无解输入。发现差异后,保留最小失败用例作为回归测试;对于多解问题,应比较题目规定的语义,而不是机械比较两个返回对象是否完全相同。