查找未排序数组中三角形的数量

在本教程中，我们将编写 Python 程序来计算可能的三角形数量。我们给出了一个未排序的数组，需要确定可以从无序正整数数组中选择三个不同的值来形成多少个三角形。当任意两个值（或边）的和大于第三个值（或边）时，就可以形成一个三角形。

示例 -

让我们使用朴素方法来解决这个问题。

方法 - 1：朴素方法

首先，我们将使用朴素方法解决这个问题。在此方法中，我们将遵循以下步骤：

1. 初始化一个变量 `count` 来跟踪找到的三角形数量，初始值为 0。
2. 然后创建三个嵌套循环来遍历所有可能的三个数组元素组合。
3. 在最内层循环中，根据三角形不等式定理检查当前三个元素的组合是否可以形成有效的三角形：任意两条边长的和必须大于第三条边长。
4. 如果当前组合形成一个有效的三角形，则将 `count` 变量加 1。
5. 循环迭代完成后，`count` 变量将包含可形成的总三角形数量。

让我们在 Python 代码中实现上述步骤。

示例 -

输出

Number of triangles: 3

这种朴素方法的时空复杂度为 O(n³)，因为有三个嵌套循环，对于大型数组来说效率低下。然而，它为问题提供了一个直接的解决方案。

方法 - 2：使用排序

要使用排序来解决这个问题，您可以遵循以下步骤：

1. 将输入数组 `arr` 按升序排序。
2. 初始化一个变量 `count` 来跟踪三角形的数量。
3. 使用循环从左到右遍历已排序的数组。对于索引 `i` 处的每个元素 `arr[i]`，执行以下步骤：
   1. 初始化两个指针 `left` 和 `right`，其中 `left` 指向第一个元素（索引 0），`right` 指向 `arr[i]` 前面的元素。
   2. 当 `left` 小于 `right` 时，检查 `arr[left] + arr[right] > arr[i]`。如果满足此条件，则表示可以与 `arr[i]`、`arr[left]` 和 `arr[right]` 形成三角形。将 `count` 增加可形成的有效三角形数量，即 `right - left`。
   3. 如果不满足条件，则将 `right` 指针减 1 以探索较小的值。
4. 循环完成后，`count` 将包含可形成的三角形总数。
5. 将 `count` 的值作为输出返回。

让我们理解以下示例 -

示例 -

输出

Number of triangles (arr1): 3
Number of triangles (arr2): 6

用于计算排序数组中三角形数量的代码的时间复杂度为 O(n²)，其中 'n' 是输入数组 `arr` 的长度。

方法 - 3：双指针法

为了使用双指针法解决这个问题，我们可以遵循以下步骤：

1. 将输入数组按升序排序。
2. 初始化一个变量 `count` 为 0。此变量将跟踪三角形的数量。
3. 使用指针 `i` 从 0 到 `n-3` 遍历已排序的数组，其中 `n` 是数组的长度。此指针表示潜在三角形的第一条边。
4. 对于每个 `i`，将另一个指针 `left` 初始化为 `i+1`，将 `right` 初始化为 `n-1`。这两个指针表示潜在三角形的第二条和第三条边。
5. 在 `while` 循环内，检查 `arr[i] + arr[left] > arr[right]`，其中 `arr[i]`、`arr[left]` 和 `arr[right]` 表示三条边的长度。如果满足此条件，则表示可以形成一个三角形。
6. 如果满足条件，则意味着我们还可以形成以 `left+1`、`left+2`、...、`right-1` 作为第三条边的三角形，只要任意两条边长的和大于第三条边。因此，将 `count` 增加 `right - left`。
7. 如果条件不满足，则将 `right` 减 1，以减小第三条边的长度。
8. 在 `while` 循环之后，将 `left` 加 1，以考虑下一个潜在的第二条边。
9. 重复步骤 5-8，直到 `left` 大于或等于 `right`。
10. 继续外层循环，以考虑下一个潜在的第一条边 (`i`)。
11. 外层循环完成后，返回 `count` 的值，它表示三角形的总数。

下面是双指针法的 Python 代码。

示例 -

输出

Number of triangles: 3

此代码使用双指针法查找可形成的三角形数量，时间复杂度为 O(n²)。

结论

在本教程中，我们探讨了三种方法来解决在未排序数组中计数三角形的问题，其中每个三角形是通过从数组中选择三个不同的值形成的。朴素方法涉及三个嵌套循环，时间复杂度为 O(n³)，对于大型数组来说效率低下。基于排序的方法和双指针方法都提供了 O(n²) 的时间复杂度的有效解决方案。对数组进行排序使我们能够有效地将问题简化为查找有效的三角形组合。双指针方法通过消除不必要的检查进一步提高了性能。