Java 8 Stream API：高效解决“两数之和”问题-java教程-PHP中文网

Java 8 Stream API：高效解决“两数之和”问题

本文将深入探讨如何利用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 的形式。

AI建筑知识问答

用人工智能ChatGPT帮你解答所有建筑问题

查看详情

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 应用程序。

以上就是Java 8 Stream API：高效解决“两数之和”问题的详细内容，更多请关注php中文网其它相关文章！