Java 8 Stream API：高效查找数组中两数之和

霞舞

发布时间：2025-11-10 18:25:02

804人浏览过

来源于php中文网

原创

java 8 stream api：高效查找数组中两数之和

本教程深入探讨如何利用Java 8 Stream API高效解决在整数列表中查找是否存在两个数之和等于给定目标值的问题。文章将从传统的双循环方法入手，逐步优化至使用Set实现O(n)时间复杂度的迭代方案，最终详细展示如何将其转化为简洁、声明式的Stream API实现，包括带日志输出和仅返回结果的多种Stream用法，并讨论算法的注意事项。

引言：两数之和问题

在软件开发中，经常会遇到在给定整数列表中寻找特定模式的问题。其中一个经典问题是：判断列表中是否存在两个数，它们的和等于一个预设的目标值。例如，给定列表 [1, 3, 6, 9] 和目标值 8，我们需要判断是否存在 x + y = 8 的组合。

传统迭代方法：嵌套循环

最直观的解决方案是使用嵌套循环遍历所有可能的数对。这种方法简单易懂，但效率较低。

import java.util.List;

public class TwoSumFinder {

    /**
     * 使用嵌套循环查找数组中是否存在两个数之和等于目标值。
     * 时间复杂度：O(n^2)
     *
     * @param target 目标和
     * @param array  整数列表
     * @return 如果找到则返回 true，否则返回 false
     */
    public static boolean validateArrayTraditional(int target, 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 == target) {
                    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 (8): " + validateArrayTraditional(8, arrayOne)); // false
        System.out.println("传统方法 - arrayTwo (8): " + validateArrayTraditional(8, arrayTwo)); // true
    }
}

此方法的缺点在于其时间复杂度为 O(n^2)，对于大型数据集，性能会迅速下降。

立即学习“Java免费学习笔记（深入）”；

优化迭代方案：利用Set进行高效查找

为了提高查找效率，我们可以利用 Set 集合的 O(1) 平均时间复杂度查找特性。核心思想是：对于列表中的每一个数 x，我们计算它与目标值 target 的差值 complement = target - x。然后，检查这个 complement 是否已经存在于我们之前遍历过的数字集合中。

import java.util.List;
import java.util.Set;
import java.util.HashSet;

public class TwoSumFinderOptimized {

    /**
     * 使用 Set 优化查找数组中是否存在两个数之和等于目标值。
     * 时间复杂度：O(n)
     *
     * @param target 目标和
     * @param array  整数列表
     * @return 如果找到则返回 true，否则返回 false
     */
    public static boolean validateArrayOptimized(int target, List array) {
        // 将列表转换为 Set，以便进行 O(1) 查找。
        // 使用 Set.copyOf(array) 可以创建一个不可变的 Set，或者使用 new HashSet<>(array)
        Set set = new HashSet<>(array); 

        for (Integer num : array) {
            int complement = target - num;
            // 检查补数是否存在于 Set 中
            // 并且确保不是同一个数字自身相加（除非目标值是 num 的两倍且 num 在列表中出现多次）
            // 这里的 (target != 2 * num) 确保了如果列表中只有一个 '4'，
            // 目标是 '8' 时不会误判 '4 + 4' 为真。
            if (set.contains(complement) && (target != 2 * num)) {
                System.out.printf("找到 %s + %s = %s%n", num, complement, target);
                return true;
            }
        }
        System.out.printf("未找到两个数之和等于 %s%n", target);
        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("\n优化方法 - arrayOne (8): " + validateArrayOptimized(8, arrayOne)); // false
        System.out.println("优化方法 - arrayTwo (8): " + validateArrayOptimized(8, arrayTwo)); // true
    }
}

此优化方案将时间复杂度降低到 O(n)，因为我们只需要遍历列表一次，并且每次查找 Set 的操作都是常数时间。

拥抱Java 8 Stream API

Java 8 引入的 Stream API 提供了一种声明式、函数式编程风格来处理集合数据。它允许我们以更简洁、更具可读性的方式表达复杂的数据处理逻辑。我们可以将上述优化后的迭代方案转换为 Stream API 实现。

Stream API实现（带日志输出）

如果我们需要在找到匹配项时进行日志记录或执行其他副作用操作，可以使用 filter、findFirst、map 和 orElseGet 等 Stream 操作。

KAIZAN.ai

使用AI来改善客户服体验，提高忠诚度

下载

import java.util.List;
import java.util.Set;
import java.util.stream.Collectors; // For Set.copyOf or new HashSet

public class TwoSumFinderStream {

    /**
     * 使用 Stream API 查找数组中是否存在两个数之和等于目标值（带日志输出）。
     * 时间复杂度：O(n)
     *
     * @param target 目标和
     * @param array  整数列表
     * @return 如果找到则返回 true，否则返回 false
     */
    public static boolean validateArrayStreamWithLogging(int target, List array) {
        // 将列表转换为 Set，以便进行 O(1) 查找。
        // 使用 Set.copyOf(array) 创建一个不可变 Set 是一个好习惯。
        Set set = Set.copyOf(array);

        return array.stream()
            // 过滤出满足条件的数字：其补数存在于 Set 中，且不是同一个数字自身相加
            .filter(num -> set.contains(target - num) && (target != 2 * num))
            // 找到第一个满足条件的数字
            .findFirst()
            // 如果找到了，执行日志输出并返回 true
            .map(num -> {
                System.out.printf("Stream API (带日志) - 找到 %s + %s = %s%n", num, target - num, target);
                return true;
            })
            // 如果未找到，执行日志输出并返回 false
            .orElseGet(() -> {
                System.out.printf("Stream API (带日志) - 未找到两个数之和等于 %s%n", target);
                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("\n--- Stream API (带日志) ---");
        System.out.println("arrayOne (8): " + validateArrayStreamWithLogging(8, arrayOne));
        System.out.println("arrayTwo (8): " + validateArrayStreamWithLogging(8, arrayTwo));
    }
}

在这个 Stream 方案中：

array.stream() 将列表转换为流。
.filter(num -> set.contains(target - num) && (target != 2 * num)) 筛选出那些其“补数”存在于 Set 中的数字。target != 2 * num 条件用于避免单个数字自身相加的情况。
.findFirst() 返回一个 Optional，表示找到的第一个匹配数字（如果存在）。
.map(num -> { ... return true; }) 如果 Optional 包含值，则执行 map 中的 lambda 表达式，打印日志并返回 true。
.orElseGet(() -> { ... return false; }) 如果 Optional 为空（即没有找到匹配项），则执行 orElseGet 中的 lambda 表达式，打印日志并返回 false。

Stream API实现（仅返回布尔结果）

如果仅仅需要一个布尔结果，判断是否存在这样的数对，那么 Stream API 可以提供更简洁的解决方案，使用 anyMatch 操作。

import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

public class TwoSumFinderStreamConcise {

    /**
     * 使用 Stream API 查找数组中是否存在两个数之和等于目标值（仅返回布尔结果）。
     * 时间复杂度：O(n)
     *
     * @param target 目标和
     * @param array  整数列表
     * @return 如果找到则返回 true，否则返回 false
     */
    public static boolean validateArrayStreamConcise(int target, List array) {
        Set set = Set.copyOf(array); // 创建不可变 Set

        return array.stream()
                // 使用 anyMatch 检查是否存在任何一个元素满足条件
                .anyMatch(num -> set.contains(target - num) && (target != 2 * num));
    }

    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("\n--- Stream API (仅返回布尔结果) ---");
        System.out.println("arrayOne (8): " + validateArrayStreamConcise(8, arrayOne)); // false
        System.out.println("arrayTwo (8): " + validateArrayStreamConcise(8, arrayTwo)); // true
    }
}

anyMatch 操作在找到第一个满足条件的元素时就会短路，立即返回 true，因此效率很高。这是在只关心是否存在匹配项时最推荐的 Stream 解决方案。

算法考量与注意事项

时间复杂度: 无论是优化的迭代方案还是 Stream API 方案，其核心算法都是基于 Set 的 O(1) 查找特性，因此整体时间复杂度为 O(n)，其中 n 是列表中的元素数量。这远优于传统嵌套循环的 O(n^2)。
空间复杂度: 使用 Set 会引入额外的空间复杂度，通常为 O(n)，用于存储列表中的所有元素。
重复数字处理:
- 当前所有基于 Set 的解决方案都假设输入列表中没有重复数字，或者如果存在重复数字，我们只关心其数值，而不是它们在原始列表中的具体位置。
- Set 会自动去重。如果原始列表是 [4, 4, 2]，目标是 8，Set 中只会包含一个 4。此时，validateArrayOptimized(8, List.of(4, 4, 2)) 可能会因为 target != 2 * num 的条件而返回 false，因为它无法区分两个不同的 4。
- 如果问题要求必须是列表中的两个不同索引位置的数字，并且允许相同数值的数字被视为不同，则需要更复杂的逻辑，例如使用 Map 来存储数字及其出现次数。
- 本文中的 (target != 2 * num) 条件旨在防止在列表中只有一个 4 的情况下，目标 8 被误判为 4 + 4。如果允许 4 + 4 = 8 并且列表中至少有两个 4，则需要移除此条件，并确保 Set 或其他数据结构能够反映出重复数字的存在。
Set 的选择:
- new HashSet(array): 创建一个可变的 HashSet，允许后续添加或删除元素。
- Set.copyOf(array) (Java 10+): 创建一个不可变的 Set。如果集合内容不会改变，使用不可变集合可以提高安全性、可预测性，并可能在某些场景下提升性能。

总结

本教程从一个常见的两数之和问题出发，逐步展示了从低效的嵌套循环到高效的 Set 优化迭代方案，最终深入探讨了如何利用 Java 8 Stream API 以更现代、更声明式的方式解决这一问题。通过 filter、findFirst、map、orElseGet 和 anyMatch 等 Stream 操作，我们不仅能够编写出简洁、可读性强的代码，还能在处理大数据集时获得显著的性能提升。在实际开发中，根据具体需求选择合适的 Stream 操作，能够有效提高代码质量和开发效率。

如何在数据输入中强制要求特定结尾字符串并实现循环验证

如何将 JSON 对象正确绑定到遵循驼峰命名规范的 Java POJO

如何在 Selenium Java 中校验表格列位置（从右向左计数）

如何在 Selenium Java 中校验表格列位置（从右数第 N 列）

如何在 JPA 原生查询中正确处理 Oracle 的日期字段格式