题目描述
给定一个包含非负整数的数组 nums，返回其中可以组成三角形三条边的三元组个数。
示例 1: 输入：nums = [2,2,3,4] 输出：3 解释：有效的组合是：(2,3,4)（使用第一个 2）、(2,3,4)（使用第二个 2）、(2,2,3)
示例 2: 输入：nums = [4,2,3,4] 输出：4
提示:
- 1 <= nums.length <= 1000
- 0 <= nums[i] <= 1000
解题思路
要判断三条边能否构成三角形，核心依据是三角不等式：任意两边之和大于第三边。对于三条边 $a, b, c$，需满足 $a+b>c$，$a+c>b$，且 $b+c>a$。
如果我们将数组先进行排序，假设选取的三条边为 $a \le b \le c$，那么只需验证 $a+b>c$ 即可。因为 $c$ 是最大的边，$a+c>b$ 和 $b+c>a$ 必然成立。这一性质大大简化了判断逻辑。
基于这个性质，我们可以采用'排序 + 双指针'的策略来降低时间复杂度，避免暴力枚举带来的 $O(N^3)$ 开销。
具体做法是固定最长边 nums[k]，然后在 [0, k-1] 范围内寻找满足条件的两个较短边。设左指针 left 指向起始位置，右指针 right 指向 k-1。
若 nums[left] + nums[right] > nums[k]，说明当前 nums[right] 与 nums[k] 搭配时，从 left 到 right-1 的所有元素都能与它们构成三角形（因为数组已排序，左侧元素更大）。此时符合条件的组合数为 right - left，随后将 right 左移继续尝试。
若和不满足条件，则说明 nums[left] 太小，无法与 nums[right] 配合超过 nums[k]，只能将 left 右移增大数值。
遍历完所有可能的最长边后，累加计数即为结果。
代码实现
class Solution {
public int triangleNumber(int[] nums) {
int n = nums.length;
// 先排序，确保 a <= b <= c 的顺序
Arrays.sort(nums);
int count = 0;
// 固定最长边，从倒数第三个开始向前遍历
for (int k = n - 1; k >= 2; k--) {
int left = 0;
int right = k - 1;
while (left < right) {
if (nums[left] + nums[right] > nums[k]) {
// 若满足条件，则 left 到 right-1 之间的所有数与 right, k 均构成三角形
count += right - left;
right--;
} else {
// 不满足，left 太小，需要增大
left++;
}
}
}
return count;
}
}
该解法的时间复杂度主要取决于排序和双指针遍历，整体为 $O(N^2)$，空间复杂度为 $O(1)$（不计排序栈开销），能够高效处理题目给定的数据规模。