本文将深入探讨如何利用java 8 stream api优化经典的“两数之和”算法问题。我们将从传统的o(n^2)双循环解法出发，逐步引入基于哈希集合（set）的o(n)迭代优化方案，并最终展示如何将此高效算法优雅地转换为简洁、声明式的stream api实现，包括带日志输出和仅返回结果的多种形式，旨在提升代码的可读性和执行效率。
在软件开发中，“两数之和”是一个经典的算法问题：给定一个整数列表和一个目标和，判断列表中是否存在两个数，它们的和等于目标和。这个问题在面试和日常开发中都非常常见，其解法效率对于大规模数据处理至关重要。
传统双循环解法及其局限性
最直观的解决方案是使用嵌套循环遍历列表中的所有可能对。对于一个包含 n 个元素的列表，我们需要选择第一个数，然后遍历剩余的数来寻找它们的和是否等于目标值。
import java.util.List;
public class Main {
static boolean validateArray(int result, List<Integer> array){
// 遍历所有可能的数对
for (int i = 0; i < array.size() - 1; i++){
for (int j = i + 1; j < array.size(); j ++){
int value1 = array.get(i);
int value2 = array.get(j);
if(value1 + value2 == result){
return true; // 找到即返回
}
}
}
return false; // 未找到
}
public static void main(String[] args) {
List<Integer> arrayOne = List.of(1, 3, 6, 9);
List<Integer> arrayTwo = List.of(1, 6, 2, 10);
System.out.println("ArrayOne 包含和为 8 的两数: " + validateArray(8, arrayOne)); // false
System.out.println("ArrayTwo 包含和为 8 的两数: " + validateArray(8, arrayTwo)); // true (6+2=8)
}
}这种方法的代码简洁易懂，但其时间复杂度为 O(n^2)。当列表 array 的规模 n 变得非常大时，这种二次方的时间复杂度会导致性能急剧下降，不适用于对效率要求较高的场景。
基于哈希集合（Set）的优化迭代方案
为了提高查找效率，我们可以利用哈希集合（Set）的特性。Set 提供了平均 O(1) 的查找时间复杂度。算法思想如下：
立即学习“Java免费学习笔记（深入）”；
- 将输入列表中的所有元素存入一个哈希集合中。
- 遍历列表中的每一个元素 x。
- 对于每个 x，计算其“补数” complement = target - x。
- 检查哈希集合中是否包含 complement。
- 为了避免同一个元素被自身匹配（例如，目标和为 8，列表中只有一个 4，我们不希望 4+4=8 成立），需要额外判断 complement != x。
import java.util.List;
import java.util.Set;
import java.util.HashSet;
public class OptimizedFinder {
static boolean findSumPair(int target, List<Integer> array) {
// 将列表元素复制到Set中，实现O(1)查找
Set<Integer> set = new HashSet<>(array); // 或者 Set.copyOf(array) 如果List是不可变的
for (Integer num : array) {
int complement = target - num;
// 检查补数是否存在于Set中，并且补数不能是当前数字本身
// (除非目标和是当前数字的两倍，且列表中有多个该数字，但通常我们找的是两个不同的数字)
if (set.contains(complement) && (target != 2 * num)) {
System.out.printf("找到 %d + %d = %d%n", num, complement, target);
return true;
}
}
System.out.printf("未找到和为 %d 的两数%n", target);
return false;
}
public static void main(String[] args) {
List<Integer> arrayOne = List.of(1, 3, 6, 9);
List<Integer> arrayTwo = List.of(1, 6, 2, 10);
List<Integer> arrayThree = List.of(4, 5, 3); // 目标8，但只有一个4
System.out.println("ArrayOne 包含和为 8 的两数: " + findSumPair(8, arrayOne));
System.out.println("ArrayTwo 包含和为 8 的两数: " + findSumPair(8, arrayTwo));
System.out.println("ArrayThree 包含和为 8 的两数: " + findSumPair(8, arrayThree));
}
}此优化方案的时间复杂度为 O(n)，因为我们只进行了一次列表遍历，并且每次查找 Set 的操作都是常数时间。空间复杂度为 O(n)，用于存储 Set。
利用Java 8 Stream API实现高效查找
Java 8 引入的 Stream API 提供了一种更声明式、更函数式的方式来处理集合数据。我们可以将上述基于 Set 的优化方案优雅地转换为 Stream API 的形式。
Stream API 简介
Stream API 允许我们以一种管道（pipeline）的方式对集合进行操作，例如过滤（filter）、映射（map）、查找（findFirst）等。它强调“做什么”而不是“怎么做”，提高了代码的可读性和简洁性。
带日志输出的Stream方案
如果我们需要在找到匹配对时输出日志信息，并返回布尔结果，可以结合 findFirst() 和 map() / orElseGet()：
import java.util.List;
import java.util.Set;
import java.util.HashSet;
public class StreamFinderWithLog {
static boolean findSumPairWithLog(int target, List<Integer> array) {
Set<Integer> set = new HashSet<>(array); // 创建哈希集合用于O(1)查找
return array.stream() // 将列表转换为Stream
.filter(num -> { // 过滤操作：查找满足条件的数字
int complement = target - num;
// 确保补数存在且不等于当前数字（避免自身匹配）
return set.contains(complement) && (target != 2 * num);
})
.findFirst() // 找到第一个满足条件的数字
.map(num -> { // 如果找到了，执行此操作（带日志）
System.out.printf("Stream API (带日志): 找到 %d + %d = %d%n", num, target - num, target);
return true;
})
.orElseGet(() -> { // 如果未找到，执行此操作（带日志）
System.out.printf("Stream API (带日志): 未找到和为 %d 的两数%n", target);
return false;
});
}
public static void main(String[] args) {
List<Integer> arrayOne = List.of(1, 3, 6, 9);
List<Integer> arrayTwo = List.of(1, 6, 2, 10);
findSumPairWithLog(8, arrayOne);
findSumPairWithLog(8, arrayTwo);
}
}此方案通过 filter 筛选出满足条件的数字，然后 findFirst 终止流并返回一个 Optional<Integer>。接着，map 和 orElseGet 方法用于处理 Optional 的存在与否，并分别执行相应的日志输出和结果返回逻辑。
精简的Stream方案（仅返回布尔结果）
如果仅仅需要判断是否存在这样的数对，而不需要额外的日志输出，Stream API 提供了更简洁的 anyMatch() 方法：
import java.util.List;
import java.util.Set;
import java.util.HashSet;
public class StreamFinderSimple {
static boolean findSumPairSimple(int target, List<Integer> array) {
Set<Integer> set = new HashSet<>(array); // 创建哈希集合
return array.stream()
.anyMatch(num -> { // 使用anyMatch判断是否存在满足条件的元素
int complement = target - num;
return set.contains(complement) && (target != 2 * num);
});
}
public static void main(String[] args) {
List<Integer> arrayOne = List.of(1, 3, 6, 9);
List<Integer> arrayTwo = List.of(1, 6, 2, 10);
System.out.println("Stream API (精简): ArrayOne 包含和为 8 的两数: " + findSumPairSimple(8, arrayOne));
System.out.println("Stream API (精简): ArrayTwo 包含和为 8 的两数: " + findSumPairSimple(8, arrayTwo));
}
}anyMatch() 方法在流中找到第一个满足条件的元素时就会立即返回 true，否则在遍历完整个流后返回 false，这与我们寻找是否存在匹配对的需求完美契合，并且代码极其简洁。
算法原理与关键考量
- Set 的 O(1) 查找优势：所有基于 Set 的解决方案都利用了哈希集合平均 O(1) 的查找时间复杂度。这是将算法从 O(n^2) 优化到 O(n) 的核心。
- *`target != 2 num条件**：此条件用于确保我们找到的是两个“不同”的数字。例如，如果目标和是 8，列表中只有一个 4，我们通常不希望4 + 4 = 8` 被视为一个有效的匹配。如果允许同一个数字被自身匹配（即列表中有两个或更多 4），则可以移除此条件。然而，根据常见问题表述，通常是指列表中两个不同位置的数字。
-
输入列表的重复元素处理：
- 如果输入 List 包含重复元素（例如 [4, 4, 1]），将其转换为 Set 会自动去重（变为 [1, 4]）。
- 如果目标是 8，且列表为 [4, 4, 1]，Set 为 [1, 4]。
- 当 num 为第一个 4 时，complement 为 4。set.contains(4) 为 true，target != 2 * num 为 false (8 != 2*4)。因此，findSumPair 会跳过此情况。
- 这种处理方式符合“寻找两个不同的数”的语义。如果需要考虑两个相同值但不同索引的元素，则需要更复杂的逻辑，例如使用 Map<Integer, Integer> 存储数字及其出现的次数。但对于大多数“两数之和”问题，当前 Set 方案是高效且符合预期的。
- Set.copyOf(array) 与 new HashSet<>(array)：Set.copyOf(array) 在 Java 9+ 中可用，它返回一个不可变的 Set，性能可能略优，且更安全。new HashSet<>(array) 适用于所有 Java 8+ 版本，返回一个可变的 HashSet。根据实际需求选择。
总结
本文从经典的“两数之和”问题出发，详细介绍了从低效的 O(n^2) 双循环解法到高效的 O(n) 基于哈希集合的迭代方案，并最终展示了如何利用 Java 8 Stream API 将其进一步优化为声明式、简洁且易读的代码。Stream API 结合适当的数据结构（如 Set），能够显著提升处理集合数据的效率和代码的优雅性。在实际开发中，理解并灵活运用这些技术，将有助于编写出更健壮、更高性能的 Java 应用程序。
