Find Triplets with Zero Sum in Java

查找零和三元组问题涉及识别数组中的三个数字，它们的总和为零。这个问题在编码面试中很常见，有助于加深对数组操作和排序技术的理解。高效的解决方案通常利用排序和双指针方法来实现最佳性能。

输入：数组 = [-3, 1, 2, -1, 5, -2]

输出：零和三元组：[[-3, -2, 5], [-3, 1, 2]]

解释

在输出中，三元组 [-3, -2, 5] 和 [-3, 1, 2] 的总和都为零。每个三元组由来自 数组 的三个数字组成，它们共同满足零和条件。我们通过排序和应用双指针技术，有效地找到这些唯一的解决方案，而不会产生重复。

方法 1：使用双指针方法

步骤 1：对数组进行排序：首先将数组按升序排序。排序有助于我们更有效地管理三元组的搜索，因为它允许我们使用双指针方法，该方法在查找特定和的对方面效率很高。

步骤 2：遍历数组：循环遍历数组中的每个元素，直到倒数第三个元素。将每个元素视为可能的三元组中的第一个元素。对于索引 i 处的每个元素，目标是使用两个指针查找另外两个元素，这些元素与 arr[i] 一起加起来为零。

步骤 3：设置双指针：对于当前元素 arr[i]，初始化两个指针：left 指针从 i 之后（即 i + 1）开始，right 指针从数组末尾（即 arr.length - 1）开始。这些指针将用于查找总和为 arr[i] 的负数的两个数字。

步骤 4：计算总和并调整指针：计算 arr[i]、arr[left] 和 arr[right] 的总和。如果总和为零，则表示您找到了一个满足条件的三元组。将此三元组添加到结果列表中。将 left 指针向右移动以跳过任何重复值，并避免重复三元组。同样，将 right 指针向左移动以跳过重复值。

步骤 4.1：如果总和小于零，则表示 left 指处的值太小，无法与 arr[i] 和 arr[right] 结合得到零。将 left 指针向右移动一步以增加总和。如果总和大于零，则 right 指处的值太大，因此将 right 指针向左移动一步以减小总和。

步骤 5：对所有元素重复：对数组中的每个元素 arr[i] 重复此过程，直到检查完所有可能的三元组。在每次循环开始时跳过重复值，以确保只有唯一的三元组添加到结果列表中。

步骤 6：返回结果：循环完成后，零和三元组的唯一列表将准备就绪。

文件名：ZeroSumTriplets.java

输出

 
Triplets with zero sum: [[-3, -2, 5], [-3, 1, 2]]   

复杂度分析

时间复杂度

此算法的时间复杂度为 O(n²)。对数组进行排序需要 O(nlogn) 时间，查找三元组需要 O(n²) 时间，因为对于每个元素，两个指针都会扫描剩余的数组。因此，主要因素是 O(n²)，这使得这种方法效率很高。

空间复杂度

如果我们忽略输出列表，此算法的空间复杂度为 O(1)，因为它是在原地对数组进行排序，并且只使用了少量额外的 变量。但是，如果我们包括三元组的输出列表，则空间复杂度取决于找到的唯一三元组的数量。

方法 2：使用哈希

算法

步骤 1：初始化结果集：首先，创建一个集合来存储我们的三元组。使用集合可以帮助我们避免重复的三元组，因为集合不允许重复条目。

步骤 2：将每个元素作为三元组的第一个元素进行循环：我们遍历数组，将每个元素 arr[i] 视为三元组的第一个元素的潜在候选。

步骤 2.1：对于每个 arr[i]，我们将计算一个目标值，即 -arr[i]。目标值表示三元组的其余两个元素需要达到的总和，才能使整个三元组的总和为零。

步骤 3：查找总和等于目标的对：对于每个 arr[i]，创建一个新的集合（我们称之为 seenElements）来跟踪可以与数组中未来元素形成对的元素。

步骤 3.1：从 arr[i] 之后的下一个元素开始（这样我们在每一步都处理唯一的元素），遍历数组以查找两个元素，它们与 arr[i] 一起加起来为零。

步骤 4：检查补数：对于我们遇到的 arr[i] 之后的每个元素 arr[j]，计算其相对于目标的补数。这个补数是 target - arr[j]。

步骤 4.1：如果补数存在于 seenElements 中，则表示我们找到了一个对，该对与 arr[i] 一起构成一个零和三元组（arr[i]、arr[j]、补数）。对这个三元组进行排序并将其添加到我们的结果集中，以避免重复。

步骤 5：将当前元素添加到 seenElements：无论是否找到三元组，都将 arr[j] 添加到 seenElements 中，以便它可以作为未来对的潜在补数。

步骤 6：对所有元素继续：对数组中的每个元素 arr[i] 重复此过程。每次，我们将 arr[i] 视为潜在三元组的第一个元素，并使用哈希查找匹配的对。

步骤 6.1：跳过外层循环中的重复项：为了确保结果的唯一性，请跳过外层循环中 arr[i] 的任何重复值。如果 arr[i] 与 arr[i-1] 相同，则继续处理下一个元素，否则会生成重复的三元组。此步骤可防止冗余计算，并避免将重复的三元组添加到结果集中。

步骤 7：将结果集转换为列表：处理完所有元素后，将唯一三元组的集合转换为列表。这是必要的，因为最终输出应该是列表的列表，而不是集合。

步骤 8：对结果列表进行排序（可选）：为了保持一致的输出格式，请对结果列表中的每个三元组进行升序排序，并可选地对整个三元组列表进行排序。此步骤可确保在三元组顺序对测试或可读性很重要的情况下，输出是有序且易于比较的。

文件名：ZeroSumTripletsHashing.java

输出

 
Triplets with zero sum: [[-3, -2, 5], [-3, 1, 2]]   

复杂度分析

时间复杂度

时间复杂度为 O(n²)，因为我们遍历每个元素，使用一个集合以线性时间查找构成零和三元组的对。该方法有效地避免了重复项，因此，尽管我们检查了每个对一次，但它仍然是二次的，从而提供了一个优化的解决方案。

空间复杂度

在每次迭代中存储潜在对的哈希集合具有 O(n) 的空间复杂度，使我们能够有效地检查补数。此外，存储唯一三元组需要基于解决方案数量的空间，因此在最坏的情况下，复杂度近似为 O(n²)。

方法 3：使用暴力方法

算法

步骤 1：计算累积和以提高效率：为了找到满足零和条件的子集，首先计算数组的累积和。

步骤 1.1：初始化一个累积和数组，其中索引 i 处的元素存储从数组开头到 i 的所有元素的总和。它使我们能够使用两个累积和之间的差值快速计算任何子数组的总和。

步骤 2：遍历数组以查找潜在的起始点：从开头到倒数第三个元素循环遍历数组。将每个元素视为三元组的潜在起始点（即，arr[i] 将是潜在三元组中的第一个元素）。

步骤 3：使用哈希映射跟踪元素总和：对于每个起始点 i，初始化一个名为 pairSums 的哈希映射来存储可能完成零和三元组的总和。哈希映射将跟踪在从数组开头到当前索引之间已遇到的总和。

步骤 4：内部循环查找补数：在主循环（对于每个起始元素 arr[i]）内，运行另一个循环，从 i + 1 开始，遍历剩余的元素。计算零和三元组中每个索引 j 处的元素的所需补数。补数计算为 j 处的当前累积和的负值。

步骤 5：检查哈希映射中的补数：检查计算出的补数是否存在于 pairSums 映射中。如果存在，则表示数组中存在一对元素，当与 arr[i] 组合时，其总和为零。它形成一个有效的三元组。

步骤 6：将三元组添加到结果列表：如果找到有效的三元组，请将其添加到结果列表中。请注意，通过确保在存储之前对每个三元组的元素进行排序来避免添加重复的三元组。

步骤 7：使用新的成对和更新哈希映射：在检查完补数后，通过将当前元素添加为未来对的可能候选来更新 pairSums。它确保映射始终保存我们正在检查的当前子数组的潜在总和。

步骤 8：删除结果中的重复三元组：在主循环结束时，结果列表可能由于不同的位置生成相同的三元组而包含重复项。对每个三元组进行排序，并将唯一的三元组存储在一个集合中，以确保最终输出中只出现不同的三元组。

文件名：ZeroSumTripletsBruteForce.java

输出

 
Triplets with zero sum: [[-3, -2, 5], [-3, 1, 2]]   

复杂度分析

时间复杂度

时间复杂度为 O(n²)，其中 n 是数组的长度。该算法将每个元素作为起始点进行迭代，对于每个起始元素，它会使用哈希映射通过查找补数来搜索剩余的元素，从而产生二次复杂度，并通过高效的查找进行了优化。

空间复杂度

空间复杂度为 O(n)，因为使用了额外的哈希集来跟踪每个三元组的潜在补数。它有助于有效地检查现有对。最终的三元组结果列表也需要空间，但总体空间与输入数组的大小保持线性关系。