题目描述补充

题目：三角形计数

给定一个包含非负整数的数组（或列表），数组中的每个数字代表一个平面上点的x坐标（假设所有点的y坐标均为0，即所有点都在x轴上）。现需要找出这些点中能够组成三角形的三个点的组合数量。三角形的要求是：任意两点之间的距离作为三角形的两边，需要满足三角形的两边之和大于第三边的条件。

示例：

• 输入：[2, 2, 3, 4]
• 输出：3
  • 解释：能够组成三角形的组合有(2, 3, 4)，(2, 4, 3)，(3, 4, 2)。注意，由于点相同但顺序不同也被视为不同的组合，因此上述三个组合都是有效的。但(2, 2, 3)不是有效的三角形，因为两边之和并不总是大于第三边。

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 代码示例

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 代码示例

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

码小课网站中有更多相关内容分享给大家学习，欢迎访问码小课获取更多编程算法、数据结构及面试技巧等资源。