本文探讨如何利用Java 8 Stream API优化在整数列表中查找两个数之和等于特定目标值的问题。通过引入Set数据结构将传统嵌套循环的O(n²)时间复杂度优化至O(n)，并进一步展示了如何将这种高效的迭代方法转换为简洁、声明式的Stream API实现，包括带日志输出和仅返回布尔结果的两种形式，从而提升代码的可读性和执行效率。
问题描述与传统方法回顾
在软件开发中，我们经常会遇到需要在给定整数列表中寻找满足特定条件的元素组合。一个常见的例子是：判断列表中是否存在两个数，它们的和等于一个预设的目标值。
传统的解决方案通常采用嵌套循环的方式，遍历所有可能的数对。例如，以下代码展示了如何使用两层for循环来解决这个问题：
import java.util.List;
public class TwoSumTraditional {
static boolean validateArray(int result, List 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 arrayOne = List.of(1, 3, 6, 9);
List arrayTwo = List.of(1, 6, 2, 10);
System.out.println("ArrayOne contains two numbers summing to 8: " + validateArray(8, arrayOne)); // false
System.out.println("ArrayTwo contains two numbers summing to 8: " + validateArray(8, arrayTwo)); // true
}
} 这种方法的优点是直观易懂，但其时间复杂度为O(N²)，其中N是列表中的元素数量。当列表非常大时，这种二次方的时间复杂度会导致性能急剧下降。
立即学习“Java免费学习笔记（深入）”；
优化方案：基于Set的迭代方法
为了提高效率，我们可以利用Set数据结构进行优化。Set的contains()方法提供了平均O(1)的查找时间复杂度。通过将列表中的所有元素放入一个Set中，我们可以在O(N)的时间内遍历列表，并对每个元素执行O(1)的查找操作，从而将整体时间复杂度降低到O(N)。
核心思想是：对于列表中的每一个数x，我们计算其“补数”complement = target - x。如果这个complement存在于Set中，并且complement不是x本身（除非target是2 * x），那么我们就找到了满足条件的两个数。
以下是基于Set的迭代实现：
import java.util.List;
import java.util.Set;
public class TwoSumOptimizedIterative {
static boolean validateArrayOptimized(int result, List array) {
Set set = Set.copyOf(array); // 将列表元素复制到Set中，以便进行快速查找
for (Integer num : array) {
int complement = result - num;
// 检查补数是否存在于Set中，并且避免同一个数字被使用两次来形成目标和
// 例如，如果目标是8，当前数字是4，补数也是4。
// 此时需要确保列表中至少有两个4，或者目标不是2*num。
// 这里的条件 (result != 2 * num) 是为了处理当 num == complement 时的特殊情况，
// 即如果目标值是当前数字的两倍，需要确保Set中存在除当前数字外的另一个相同值。
// 由于Set存储的是唯一元素，此实现假设输入列表中没有重复元素。
// 如果允许重复，则需要更复杂的逻辑，例如使用Map存储计数。
if (set.contains(complement) && (result != 2 * num || (result == 2 * num && countOccurrences(array, num) > 1))) {
// 为了简化，我们通常假设 (result != 2 * num) 已经足够，或者Set是基于原始列表构建的。
// 如果原始列表可以有重复，且希望找到两个不同的索引，则Set方案需要调整。
// 在本例中，我们主要关注是否存在两个“值”，而不是两个“索引”。
// 最简洁且符合Set特性的做法是：
if (set.contains(complement) && (num != complement || (num == complement && countOccurrences(array, num) > 1))) {
// 修正：如果 num == complement，意味着 target = 2 * num，我们需要确保有两个 num。
// 但 Set.copyOf(array) 会去重。所以更准确的判断是 (num != complement)
// 或者如果 num == complement，需要检查原始列表中是否有重复。
// 考虑到Set去重，我们通常简化为：
if (num != complement) { // 找到两个不同的数
System.out.printf("Found %s + %s = %s%n", num, complement, result);
return true;
} else if (countOccurrences(array, num) > 1) { // 找到两个相同的数
System.out.printf("Found %s + %s = %s%n", num, complement, result);
return true;
}
}
}
}
System.out.printf("Did not find two numbers their addition would result in %s%n", result);
return false;
}
// 辅助方法：计算元素在列表中出现的次数
private static long countOccurrences(List array, int target) {
return array.stream().filter(i -> i == target).count();
}
public static void main(String[] args) {
List arrayOne = List.of(1, 3, 6, 9);
List arrayTwo = List.of(1, 6, 2, 10);
List arrayThree = List.of(4, 2, 6); // Test case for target = 8, num = 4
System.out.println("ArrayOne (8): " + validateArrayOptimized(8, arrayOne)); // false
System.out.println("ArrayTwo (8): " + validateArrayOptimized(8, arrayTwo)); // true (6+2)
System.out.println("ArrayThree (8): " + validateArrayOptimized(8, arrayThree)); // false (no two 4s)
List arrayFour = List.of(4, 4, 1, 3);
System.out.println("ArrayFour (8): " + validateArrayOptimized(8, arrayFour)); // true (4+4)
}
} 注意： 上述代码中的 (result != 2 * num || (result == 2 * num && countOccurrences(array, num) > 1)) 这一条件处理了目标值是当前数字两倍（即 num == complement）的情况。由于 Set 会自动去重，如果原始列表中只包含一个 num，那么 set.contains(complement) 即使为真，也意味着 num 自身被作为 complement 找到了，这不符合“两个数”的要求。因此，当 num == complement 时，需要额外检查原始列表中是否存在至少两个 num。如果输入列表保证没有重复元素，则可以直接使用 set.contains(complement) && num != complement。
拥抱Java 8 Stream API
Java 8引入的Stream API提供了一种更函数式、声明式的方式来处理集合数据。它可以将上述迭代逻辑转换为更简洁、更易读的代码。
Stream API实现（带日志输出）
如果我们需要在找到满足条件的数对时打印日志信息，可以使用filter、findFirst、map和orElseGet等Stream操作符：
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;
public class TwoSumStreamWithLogging {
static boolean validateArrayWithStreamLogging(int result, List array) {
Set set = array.stream().collect(Collectors.toSet()); // 将列表元素收集到Set中
return array.stream()
.filter(num -> {
int complement = result - num;
// 同样处理 num == complement 的情况
return set.contains(complement) && (num != complement || (num == complement && array.stream().filter(i -> i == num).count() > 1));
})
.findFirst() // 找到第一个满足条件的元素
.map(num -> { // 如果找到了，执行此lambda表达式
int complement = result - num;
System.out.printf("Found %s + %s = %s%n", num, complement, result);
return true;
})
.orElseGet(() -> { // 如果没有找到，执行此lambda表达式
System.out.printf("Did not find two numbers their addition would result in %s%n", result);
return false;
});
}
public static void main(String[] args) {
List arrayOne = List.of(1, 3, 6, 9);
List arrayTwo = List.of(1, 6, 2, 10);
List arrayThree = List.of(4, 2, 6);
List arrayFour = List.of(4, 4, 1, 3);
System.out.println("ArrayOne (8): " + validateArrayWithStreamLogging(8, arrayOne));
System.out.println("ArrayTwo (8): " + validateArrayWithStreamLogging(8, arrayTwo));
System.out.println("ArrayThree (8): " + validateArrayWithStreamLogging(8, arrayThree));
System.out.println("ArrayFour (8): " + validateArrayWithStreamLogging(8, arrayFour));
}
} 在这个Stream管道中：
- array.stream()：创建列表的流。
- filter(num -> ...)：过滤元素。对于每个元素num，它检查其补数是否存在于Set中，并处理了num == complement的特殊情况。
- findFirst()：返回一个Optional
，其中包含第一个满足filter条件的元素（如果存在）。 - map(num -> { ... })：如果Optional中存在值，则执行此映射操作，打印日志并返回true。
- orElseGet(() -> { ... })：如果Optional为空（即没有找到满足条件的元素），则执行此操作，打印未找到的日志并返回false。
Stream API实现（简洁版）
如果仅仅需要一个布尔结果，判断是否存在这样的数对，而不需要任何日志输出，那么Stream API可以进一步简化，使用anyMatch()方法：
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;
public class TwoSumStreamConcise {
static boolean validateArrayWithStreamConcise(int result, List array) {
Set set = array.stream().collect(Collectors.toSet());
return array.stream()
.anyMatch(num -> {
int complement = result - num;
return set.contains(complement) && (num != complement || (num == complement && array.stream().filter(i -> i == num).count() > 1));
});
}
public static void main(String[] args) {
List arrayOne = List.of(1, 3, 6, 9);
List arrayTwo = List.of(1, 6, 2, 10);
List arrayThree = List.of(4, 2, 6);
List arrayFour = List.of(4, 4, 1, 3);
System.out.println("ArrayOne (8): " + validateArrayWithStreamConcise(8, arrayOne));
System.out.println("ArrayTwo (8): " + validateArrayWithStreamConcise(8, arrayTwo));
System.out.println("ArrayThree (8): " + validateArrayWithStreamConcise(8, arrayThree));
System.out.println("ArrayFour (8): " + validateArrayWithStreamConcise(8, arrayFour));
}
} anyMatch(predicate)方法会检查流中的任何元素是否满足给定的谓词（Predicate）。一旦找到第一个匹配的元素，它就会短路并立即返回true，否则在遍历完所有元素后返回false。这种方式代码更加简洁，表达意图也更加清晰。
算法分析与注意事项
-
时间复杂度：
- 传统嵌套循环方法：O(N²)。
- 基于Set的迭代方法和Stream API方法：O(N)。这是因为将列表元素放入Set需要O(N)时间（平均），然后遍历列表并进行Set查找（O(1)平均）总共也是O(N)时间。
-
空间复杂度：
- 传统嵌套循环方法：O(1)（不考虑输入列表本身）。
- 基于Set的方法：O(N)，因为需要额外的空间来存储Set。
-
重复元素处理：
- 上述Set和Stream方案在处理target = 2 * num且列表中只有一个num时，需要额外的逻辑（如countOccurrences）来确保是“两个数”的和。如果输入列表保证没有重复元素，则可以简化条件为 set.contains(complement) && num != complement。
- 如果问题要求找到两个不同索引的数，即使它们的值相同，那么Set方案需要进一步修改，例如使用Map
>来存储值及其所有索引，或者直接使用原始的O(N²)方案，或者对O(N)方案进行更复杂的改造。本文主要关注“值”的匹配。
总结
通过引入Set数据结构，我们能够将查找数组中两数之和问题的算法复杂度从O(N²)显著优化到O(N)。在此基础上，Java 8的Stream API提供了一种更加优雅和声明式的方式来实现这一优化逻辑。无论是需要详细的日志输出还是仅仅一个布尔结果，Stream API都能以简洁、可读性强的方式表达算法意图，是现代Java开发中处理集合数据时值得优先考虑的工具。在实际应用中，根据具体需求（如是否需要日志、是否允许重复元素、是否关注索引等），选择最合适的实现方案至关重要。
