在本教程中，我们将编写 Python 程序来计算三角形的可能数量。我们给出了一个未排序的数组，我们需要确定使用来自正整数的无序数组中的三个不同值可以创建多少个三角形。当任意两个值（或边）之和大于第三个值（或边）时，可以形成三角形。
案例1：
输入: arr = [5, 8, 11, 15]
输出: 4
说明可以形成四个三角形: {5, 8, 11}, {8, 11, 15}, {5, 11, 15}, and {5, 8, 15}.
案例2：
输入: arr = [2, 4, 6, 10, 12, 14, 16]
输出: 20
说明可能有 20 个三角形，包括{2, 4, 6}, {4, 6, 10}, {6, 10, 12}, {10, 12, 14}, {2, 6, 10}, {4, 10, 14}, {6, 12, 16}, {2, 6, 12}, {4, 10, 16}, {2, 10, 12}, {4, 6, 12}, {10, 12, 16}, {2, 4, 10}, {6, 12, 14}, {2, 4, 12}, {4, 6, 16}, {6, 10, 16}, {2, 6, 16}, {4, 12, 16}, 和{2, 10, 16}.
方法 - 1：天真方法
首先，我们将使用天真法来解决这个问题。在这种方法中，我们将遵循以下步骤
- 初始化一个变量 count，用于跟踪找到的三角形数量，初始值设为 0。
- 然后创建三个嵌套循环，遍历三个数组元素的所有可能组合。
- 在最内层循环中，根据三角形不等式定理：任意两条边的长度之和必须大于第三条边的长度，检查当前三个元素的组合是否能构成一个有效的三角形。
- 如果当前组合形成了一个有效的三角形，则计数变量递增 1。
- 循环迭代结束后，计数变量将包含可形成的三角形总数。
def count_triangles_naive(arr):
n = len(arr)
count = 0
# 迭代三个元素的所有可能组合 ；
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
# Check if the current combination forms a valid triangle
if (
arr[i] + arr[j] > arr[k]
and arr[j] + arr[k] > arr[i]
and arr[k] + arr[i] > arr[j]
):
count += 1
return count
arr = [4, 6, 3, 7]
result = count_triangles_naive(arr)
print("Number of triangles:", result)
|
输出：
Number of triangles: 3
由于存在三个嵌套循环，这种简单方法的时间复杂度为 O(n3)，因此对于大型数组来说效率很低。不过，它提供了一个简单直接的解决方案。
方法 - 2：使用排序
要使用排序解决此问题，您可以按照以下步骤操作：
- 按升序对输入数组 arr 进行排序。
- 初始化变量 count 来跟踪三角形的数量。
- 使用循环从左到右迭代排序后的数组。对于索引 i 处的每个元素 arr，执行以下步骤：
- 初始化两个指针，left和right，其中left指向第一个元素（索引0），right指向arr之前的元素。
- 当左小于右时，检查 arr[left] + arr[right] 是否 > arr。如果满足此条件，则表示可以用 arr、arr[left] 和 arr[right] 组成三角形。用可以形成的有效三角形个数递增计数，即右-左。
- 如果不满足条件，则递减右指针以探索更小的值。
- 循环完成后，count 将包含可以形成的三角形的总数。
- 返回 count 的值作为输出。
def countTriangles(arr):
n = len(arr)
arr.sort()
count = 0
for i in range(n - 1, 1, -1):
left, right = 0, i - 1
while left < right:
if arr[left] + arr[right] > arr[i]:
# Triangles can be formed with arr[i], arr[left], and arr[right]
count += right - left
right -= 1
else:
# Move left pointer to explore larger values
left += 1
return count
arr1 = [4, 6, 3, 7]
arr2 = [10, 21, 22, 100, 101, 200, 300]
output1 = countTriangles(arr1)
output2 = countTriangles(arr2)
print("Number of triangles (arr1):", output1)
print("Number of triangles (arr2):", output2)
|
计算排序数组中三角形个数的代码的时间复杂度为 O(n^2)，其中 "n "为输入数组 arr 的长度。
方法 - 3：双指针法
要使用双指针法解决这个问题，我们可以遵循以下步骤：
[list=1]
按升序排列输入数组。
将变量 `count` 初始化为 0，该变量将记录三角形的数量。
使用从 0 到 `n-3` 的指针 `i` 遍历排序后的数组，其中 `n` 是数组的长度。该指针代表潜在三角形的第一条边。
对于每个 `i`，将另一个指针 `left` 初始化为 `i+1`，将 `right` 初始化为 `n-1`。这两个指针分别代表潜在三角形的第二条边和第三条边。
在 while 循环中，检查 `arr + arr[left] > arr[right]`，其中 `arr`、`arr[left]` 和 `arr[right]` 代表三条边的长度。如果满足这个条件，就意味着我们可以组成一个三角形。
如果满足该条件，则意味着只要任意两条边的长度之和大于第三边，我们也可以组成以 `左+1`、`左+2`、...、`右-1` 为第三边的三角形。因此，按`右-左`递增`计数`。
如果不满足条件，则将 `right` 减 1 以减少第三边的长度。
在 while 循环后，将 `left` 递增 1，以考虑下一个可能的第二边。
重复步骤 5-8 直到 `left` 大于或等于 `right`。
继续外循环，考虑下一个潜在的第一边（`i`）。
外循环结束后，返回 `count` 的值，它代表三角形的总数。
def count_triangles(arr):
n = len(arr)
if n < 3:
return 0
# Sort the array in ascending order
arr.sort()
count = 0
for i in range(n - 2):
left, right = i + 1, n - 1
while left < right:
if arr[i] + arr[left] > arr[right]:
如果三角形是可能的，那么以left，left+1,，...，right-1为第三边的三角形也是可能的 ；
count += right - left
right -= 1
else:
left += 1
return count
arr = [4, 6, 3, 7]
result = count_triangles(arr)
print("Number of triangles:", result)
|
该代码可以找出使用双指针方法可以形成的三角形数量，时间复杂度为 O(n^2)。
结论
在本教程中，我们探索了三种方法来解决计算无排序数组中三角形的问题，其中每个三角形都是通过从数组中选择三个不同的值形成的。最简单的方法涉及三个嵌套循环，时间复杂度为 O(n3)，对于大型数组来说效率很低。基于排序的方法和双指针方法都提供了高效的解决方案，时间复杂度均为 O(n2)。通过对数组进行排序，我们可以将问题简化为高效地找到有效的三角形组合。双指针方法通过消除不必要的检查进一步提高了性能。