当前位置： 面试刷题>> 三角形计数 (经典算法题500道)
### 题目描述补充
**题目：三角形计数**
给定一个包含非负整数的数组（或列表），数组中的每个数字代表一个平面上点的x坐标（假设所有点的y坐标均为0，即所有点都在x轴上）。现需要找出这些点中能够组成三角形的三个点的组合数量。三角形的要求是：任意两点之间的距离作为三角形的两边，需要满足三角形的两边之和大于第三边的条件。
**示例**：
- 输入：`[2, 2, 3, 4]`
- 输出：`3`
- 解释：能够组成三角形的组合有`(2, 3, 4)`，`(2, 4, 3)`，`(3, 4, 2)`。注意，由于点相同但顺序不同也被视为不同的组合，因此上述三个组合都是有效的。但`(2, 2, 3)`不是有效的三角形，因为两边之和并不总是大于第三边。
### PHP 代码示例
```php
function countTriangles($nums) {
$count = 0;
$n = count($nums);
sort($nums); // 先对数组进行排序
for ($i = $n - 1; $i >= 2; $i--) {
$left = 0;
$right = $i - 1;
while ($left < $right) {
if ($nums[$left] + $nums[$right] > $nums[$i]) {
// 由于数组已排序，左侧的所有元素与当前右侧元素组合均满足条件
$count += $right - $left;
$right--;
} else {
$left++;
}
}
}
return $count;
}
// 示例
$nums = [2, 2, 3, 4];
echo countTriangles($nums); // 输出 3
```
### Python 代码示例
```python
def countTriangles(nums):
nums.sort() # 先对数组进行排序
n = len(nums)
count = 0
for i in range(n - 1, 1, -1):
left, right = 0, i - 1
while left < right:
if nums[left] + nums[right] > nums[i]:
# 由于数组已排序，left到right-1的所有元素与right均满足条件
count += right - left
right -= 1
else:
left += 1
return count
# 示例
nums = [2, 2, 3, 4]
print(countTriangles(nums)) # 输出 3
```
### JavaScript 代码示例
```javascript
function countTriangles(nums) {
nums.sort((a, b) => a - b); // 先对数组进行排序
let count = 0;
const n = nums.length;
for (let i = n - 1; i >= 2; i--) {
let left = 0;
let right = i - 1;
while (left < right) {
if (nums[left] + nums[right] > nums[i]) {
// 左侧的所有元素与当前右侧元素组合均满足条件
count += right - left;
right--;
} else {
left++;
}
}
}
return count;
}
// 示例
const nums = [2, 2, 3, 4];
console.log(countTriangles(nums)); // 输出 3
```
**码小课网站中有更多相关内容分享给大家学习**，欢迎访问码小课获取更多编程算法、数据结构及面试技巧等资源。