Python中求未排序数组中三角形数量的三种方法
内容提要
本教程介绍了三种计算未排序数组中可能的三角形数量的方法：三个嵌套循环、排序和双指针。排序和双指针方法可以提高计算效率。
延伸解读
从暴力枚举到排序优化：效率提升的关键
文章对比了三种方法：三重循环暴力枚举的时间复杂度为O(n³)，而基于排序和双指针的方法均为O(n²)。对于大规模数组，O(n³)的算法可能无法在合理时间内完成，而O(n²)的算法则更具实用性。这体现了算法优化中利用问题特性（如排序后的大小关系）来减少不必要的计算，是提升程序性能的常见思路。
排序如何简化三角形计数
排序后，数组元素按升序排列，这为三角形不等式提供了便利。在有序数组中，若较小的两边之和大于第三边，则其他组合也可能成立。文章中的排序方法通过固定最长边，并在其左侧使用双指针寻找满足条件的边对，从而将问题转化为线性扫描，避免了枚举所有三元组。这种基于排序的预处理是许多几何计数问题的有效策略。
双指针法的核心逻辑与计数技巧
双指针法在排序基础上，固定第一条边，用左右指针分别指向剩余部分的两端。当arr[i] + arr[left] > arr[right]时，由于数组有序，所有介于left和right之间的元素作为第三边都能与arr[i]和arr[left]构成三角形，因此可以一次性增加right-left个计数，并右移right指针。否则左移left指针。这种批量计数避免了逐个检查，是算法高效的关键。
实现时需注意的边界与细节
文章中的代码示例展示了具体实现。需要注意：双指针法中外循环i的范围是0到n-3，确保至少有三个元素；内层循环中left从i+1开始，right从n-1开始。当数组长度小于3时直接返回0。此外，排序会改变原数组顺序，若需保留原数组，应先复制。这些细节保证了算法的正确性和鲁棒性。
Q&A
如何判断三个数能否构成三角形？
根据三角形不等式定理，任意两条边的长度之和必须大于第三条边的长度。即对于三个数 a、b、c，必须满足 a + b > c、a + c > b 且 b + c > a。
计算未排序数组中三角形数量的天真方法是什么？时间复杂度如何？
天真方法使用三个嵌套循环遍历所有三个元素组合，检查每个组合是否满足三角形不等式，若满足则计数加一。时间复杂度为 O(n^3)，效率较低，不适合大型数组。
使用排序方法计算三角形数量的步骤是什么？
先对数组升序排序，然后从右向左固定最大边 arr[i]，用左右指针 left 和 right 分别指向 0 和 i-1。当 arr[left] + arr[right] > arr[i] 时，可以构成三角形，计数增加 right - left，然后 right 减一；否则 left 加一。重复直到 left >= right。
双指针法计算三角形数量的时间复杂度是多少？
双指针法的时间复杂度为 O(n^2)，其中 n 是数组长度。
排序方法和双指针法在计算三角形数量时有何区别？
排序方法固定最大边后使用左右指针向中间移动，而双指针法固定最小边后使用左右指针向中间移动。两者时间复杂度均为 O(n^2)，但双指针法通过消除不必要的检查进一步提高了性能。
对于数组 [5, 8, 11, 15]，可以形成多少个三角形？
可以形成 4 个三角形，分别是 {5, 8, 11}、{8, 11, 15}、{5, 11, 15} 和 {5, 8, 15}。
