Java 中的 Two Sum 问题

Source: Dev.to

两数之和问题 – Java 中的不同实现方式

Two‑Sum（两数之和）问题是开发者面试中最常见的题目之一。
给定一个整数数组和一个目标和，需要在数组中找到 两个数 使它们的和等于目标值。

下面给出四种经典的 Java 解法，按从最简单（但最慢）到最高效的顺序排列。

1️⃣ 暴力法（时间 O(n²)，空间 O(1)）

遍历每个元素 x，对每个 x 再扫描数组其余部分，寻找满足 x + y == target 的补数 y。

public static int[] getTargetSumIndices(int[] arr, int target) {
    for (int i = 0; i  num) {
            high = mid - 1;
        } else if (arr[mid]  seen = new HashSet<>();

    for (int x : arr) {
        int complement = target - x;
        if (seen.contains(complement)) {
            return new int[]{complement, x}; // found the pair
        }
        seen.add(x);
    }
    return new int[]{-1, -1}; // not found
}

复杂度：

• 时间 – O(n)（单次遍历，常数时间查找）。
• 空间 – O(n) 用于存放哈希集合。

汇总表

选择最适合你约束条件的实现方式：

• 如果可以接受额外空间且需要最快的运行时间 → 使用 哈希集合 方法。
• 如果必须保持 O(1) 空间且可以对数组进行重新排序 → 双指针 技巧是理想选择。
• 对于教学演示或极小规模输入，暴力法 也完全可行。

常数时间操作（ O(1) ）的插入与查找

该实现的代码如下：

public static int[] getTargetSumPair(int[] arr, int target) {
    HashSet seen = new HashSet<>();
    for (int i = 0; i < arr.length; i++) {
        int complement = target - arr[i];
        if (!seen.contains(complement)) {
            seen.add(arr[i]);
        } else {
            return new int[] { arr[i], complement };
        }
    }
    return new int[] { -1, -1 };
}

复杂度分析

• 时间复杂度： O(n) – 只遍历数组一次。
  在 HashSet 上的查找和插入操作平均为 O(1)。

• 空间复杂度： O(n) – 将每个访问过的元素存入哈希集合。

希望你喜欢这篇关于 Two Sum（两数之和）问题以及各种实现思路的博客。这是我在 dev.to 上的第一篇算法相关的博客。写博客对我来说是一个非常有趣的学习方式，能够帮助我澄清疑惑并与社区分享我的理解。我致力于用 GIF 等可视化工具以有趣的方式讲清概念。

在本篇文章之后，我会继续为开发者社区带来更多此类内容，期待大家一起阅读、成长！