Two Sum-Pairs with 0 Sum Problem in Java

Two Sum - Pairs with Zero Sum 是另一个算法问题，指的是识别数组中和为零的整数对的问题。这个问题在编码面试和竞争性编程中相当常见，因为它不仅需要数学计算，还需要对数据结构的良好操作。

尽快解决这个问题将使我们能够理解如何解决与对、和以及唯一解集相关的其他问题。

问题陈述

假设我们现在给出一个整数值数组，问题是找出所有可能的整数对 (a, b)，其中 a + b = 0。这意味着数组中的每个正整数都应该在同一个数组中有一个对应的负整数。

这个问题是如何以尽可能少的时间和空间来找到这些对。解决方案还必须考虑输入 数组 中可能重复的对，以便每个这样的对只报告一次。

解决问题的方案

可以通过几种方法来解决这个问题，其中最突出的解决方案是；使用排序数组和哈希集进行查找。然而，这两种方法都将在下面解释。

方法 1：使用哈希集

它使用一个哈希集来捕获元素，因为数组将由一个 方法 处理，稍后将进行讨论。对于每个元素，我们都需要检查其对是否存在于集合中，这对于有效的对是足够的。

文件名：TwoSumZero.java

输出

 
Pairs with zero sum:
Pair: -3,3
Pair: -1,1
Pair: -2,2   

方法 2：使用排序和双指针

这种方法更简单，并且在排序数组后减小了数组的大小；然后使用两个指针来查找和为零的两个数。这种方法很有效，并且由于数组中的元素已排序，因此重复项会自动删除。

文件名：TwoSumZero.java

输出

 
Pairs with zero sum:
Pair: -3,3
Pair: -1,1
Pair: -2,2   

复杂度分析

时间复杂度

• 哈希集方法： 平均插入和查找操作的O(N)。
• 排序和双指针方法： 由于排序，时间复杂度为O(NlogN)，然后是双指针遍历的O(N)。

空间复杂度

• 哈希集方法： 将元素存储在哈希集中为 O(N)。
• 排序和双指针方法： 如果我们忽略输入数组的空间，则额外空间为 O(1)。

结论

它们可以适当地找到构成零和结果的整数的唯一对。它们之间的选择取决于需要某些功能的场景，例如时间和 内存 要求。由于哈希集方法的时间复杂度是线性的，因此在未排序的数组中，它通常比其他方法更快。

另一方面，排序和双指针技术提供了清晰的组织，并且相似的对会被自动排除。理解这些方法不仅可以提高一个人的解决问题的能力，还可以让你为使用组合/数组中的和的更高级场景做好准备。这些技术可以极大地提高候选人在技术面试或编程竞赛中的表现。