算法题：有效三角形的个数
今天我碰到了一道算法题，题目是：有效三角形的个数。
题目大致意思就是给你一个整数数组，数组里的每个元素代表一个边长，要求你计算出能够组成三角形的边的个数。注意，组成三角形的三条边必须满足三角形的三边不等式：即三条边的长度必须满足 a + b > c、a + c > b、b + c > a。很显然，这是一个经典的排序和组合问题，但如何高效地解决它呢？
咱们先来分析下。如果我们直接遍历数组里的每一个三元组，去判断它们是否能构成三角形，那无疑是低效的，复杂度是 O(n^3) 级别的。尤其是当 n 很大时，时间复杂度就不太友好了。所以，要想提高效率，最好的办法就是先对数组排序。排序后的数组我们就可以利用“贪心”思想和双指针技巧来快速解题。
让我们从一个简单的例子开始吧：假设给定一个数组 [4, 2, 3, 6]，我们想要找出其中能组成三角形的三条边。
步骤1：排序
首先，我们对数组进行排序，这样我们可以利用数组的单调性来简化判断。排序后的数组是 [2, 3, 4, 6]。接下来，我们就可以通过遍历的方式来检查每一组三条边能否组成三角形。
步骤2：用双指针优化搜索
我们用双指针的方式来寻找符合条件的三角形边。固定一个边作为最小边，然后利用两根指针去找符合三角形不等式的其他两个边。具体实现时，我们可以固定一个 i，然后用两个指针 j 和 k，分别指向 i+1 和数组的最后一个元素。然后我们尝试让 arr[i] + arr[j] > arr[k] 成立，如果成立，说明从 j 到 k 所有的三角形都能组成有效三角形。
代码实现
import java.util.Arrays;
public class Triangle {
public int triangleNumber(int[] nums) {
// 如果数组为空或者数组的长度小于3，直接返回0
if (nums == null || nums.length < 3) return 0;
// 排序数组
Arrays.sort(nums);
int n = nums.length;
int count = 0;
// 固定最小边i
for (int i = 0; i < n - 2; i++) {
int j = i + 1, k = n - 1;
// 双指针从两端向中间收缩
while (j < k) {
if (nums[i] + nums[j] > nums[k]) {
count += (k - j); // 满足三角形条件时，所有[j, k-1] 都能组成三角形
j++; // 增大中间边
} else {
k--; // 减小最大边
}
}
}
return count;
}
public static void main(String[] args) {
Triangle solution = new Triangle();
int[] nums = {4, 2, 3, 6};
System.out.println(solution.triangleNumber(nums)); // 输出：3
}
}
代码讲解
排序： 我们首先对数组进行排序，这样可以简化判断条件。如果数组已经是升序排列，那么我们就只需要判断当前的三条边能否组成三角形。
双指针： 对于每个固定的边
i，我们通过两个指针j和k来判断能够组成有效三角形的边的个数。这样能够将时间复杂度从 O(n^3) 降低到 O(n^2)。计数： 一旦
nums[i] + nums[j] > nums[k]成立，意味着从j到k的所有组合都符合三角形不等式，因此可以直接加上k - j。然后移动指针继续尝试下一个组合。
时间复杂度
排序的时间复杂度是 O(n log n)，而双指针的搜索过程是 O(n^2)，因此总体的时间复杂度是 O(n^2)，比暴力解法 O(n^3) 提升了很多。如果数组很大，O(n^2) 的解法会显得非常高效。
结语
这道题本质上是一个排序加双指针的典型问题。通过对数组进行排序，再利用双指针来优化搜索过程，可以让我们高效地找出所有有效的三角形个数。虽然算法有点小技巧，但解决问题的思路其实很简单。
对编程、职场感兴趣的同学，可以链接我，微信：coder301 拉你进入“程序员交流群”。
