在 Python 中查找和零和的三元组

在本教程中，我们将编写 Python 程序来查找给定列表中所有和为零的三元组。我们将使用各种方法来解决这个问题。首先，让我们理解问题陈述。

问题陈述 -

给定一个包含不重复元素的列表，我们需要找到列表中和为零的三元组。

示例 -

让我们来理解解决此问题的第一种方法——

方法 1：暴力算法

这种简单的方法需要 O(n3) 的时间来解决这个问题。在此方法中，我们将遵循以下方法——

我们将运行三个 for 循环，逐个检查三个元素的和是否为零。如果三个元素的和为零，则打印元素；否则，打印未找到。

让我们来理解以下代码。

示例 -

输出

[[-20, 0, 20], [-20, 40, -20], [0, 20, -20], [0, 40, -40]]

解释 -

在上面的代码中，我们运行了三个 for 循环 i、j 和 k。第一个循环从零到 n-2，第二个 for 循环从 i+1 到 n-1，第三个循环从 j+1 到 n。循环计数器指定了三元组的三个元素。然后，我们检查 i、j、k 位置元素的和是否等于零。如果条件为真，则打印和，否则继续。

复杂度分析

• 时间复杂度：时间复杂度为 O(n³)。
  由于需要三个嵌套循环，因此时间复杂度为 O(n³)。
• 辅助空间：辅助空间为 O(1)。
  由于不需要额外的空间，因此空间复杂度是常数。

方法 2：使用哈希

在此方法中，我们将使用哈希来获得所需的结果。此方法比前一种方法更有效，因为它能在 O(N²) 的较短时间内给出结果。我们将遵循以下方法——

它涉及遍历数组。对于每个元素 list1[i]，找到一个和为“-list1[i]”的对。这个问题可以归结为对和问题，并可以用哈希在 O(n) 时间内解决。

让我们来理解以下代码——

示例 -

输出

[[0, -20, 20], [40, -20, -20], [20, 0, -20], [40, 0, -40]]

解释 -

在上面的代码中，我们创建了一个 **hashmap** 来存储键值对。然后，我们运行两个嵌套循环；外层循环从 0 到 n-2，内层循环从 i+1 到 n-1。然后，我们检查 i 和 j 元素的和乘以 -1 是否存在于 hashmap 中。

如果元素存在于 hashmap 中，则打印三元组；将 hashmap 的 j 个组件插入。

复杂度分析

• 时间复杂度：时间复杂度为 O(n²)，因为只需要两个嵌套循环，所以时间复杂度为 O(n²)。
• 辅助空间：辅助空间为 O(n)，因为需要一个 hashmap，所以空间复杂度是线性的。

方法 3：使用排序

在此方法中，我们将使用排序在 O(n²) 时间内获得合适的结果。让我们来理解以下代码。

示例 -

输出

[[-6, 1, 5], [-6, 2, 4]]

解释 -

在上面的代码中，首先，我们将数组按升序排序，然后从头到尾遍历数组。对于每个索引 i，创建两个变量 l = l + 1 和 r = n - 1。然后，我们运行一个循环直到 i 小于 r；如果 list1[i]、list1[j] 和 array[r] 的和等于零，则打印三元组并中断循环。

现在，我们检查和是否小于，如果是，则增加 l 的值；通过增加 l 的值，和将增加，因为列表已排序，所以 list1[i+1]>list1[l]。

如果和大于零，则减小 r 的值；通过减小 r 的值，和将减小，因为数组已排序，所以 list1[r-1] < list1[r]。

复杂度分析

• 时间复杂度：时间复杂度为 O(n²)，因为只需要两个嵌套循环，所以时间复杂度为 O(n²)。
• 辅助空间：辅助空间为 O(1)，因为需要一个 hashmap，所以空间复杂度是线性的。

结论

本教程包括查找三元组的各种方法。我们还实现了代码，解释了其工作原理和相应的时间复杂度。