题目描述补充

题目：合法的三角数

给定一个包含非负整数的数组，请找出数组中所有可以组成三角形的三个数的组合（每组三个数），其中三角形的形成条件是任意两边之和大于第三边。

示例

输入：[2, 2, 3, 4]

输出：[[2, 3, 4]]

解释：存在一组数 [2, 3, 4]，它们满足三角形的条件，即 2 + 3 > 4, 2 + 4 > 3, 3 + 4 > 2。

示例代码

PHP

function validTriangles($nums) {
    $result = [];
    sort($nums); // 先排序，以便从最小的数开始组合
    $n = count($nums);
    
    for ($i = 0; $i < $n - 2; $i++) {
        for ($j = $i + 1; $j < $n - 1; $j++) {
            for ($k = $j + 1; $k < $n; $k++) {
                if ($nums[$i] + $nums[$j] > $nums[$k]) {
                    $result[] = [$nums[$i], $nums[$j], $nums[$k]];
                }
                // 如果当前最小的两个数之和都小于等于第三大的数，则无需继续检查后面的数
                if ($nums[$i] + $nums[$j] <= $nums[$k]) {
                    break;
                }
            }
        }
    }
    
    return $result;
}

// 示例
$nums = [2, 2, 3, 4];
$triangles = validTriangles($nums);
print_r($triangles);

Python

def valid_triangles(nums):
    nums.sort()  # 排序
    result = []
    n = len(nums)
    
    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            for k in range(j + 1, n):
                if nums[i] + nums[j] > nums[k]:
                    result.append([nums[i], nums[j], nums[k]])
                # 剪枝
                if nums[i] + nums[j] <= nums[k]:
                    break
    
    return result

# 示例
nums = [2, 2, 3, 4]
triangles = valid_triangles(nums)
print(triangles)

JavaScript

function validTriangles(nums) {
    nums.sort((a, b) => a - b); // 排序
    const result = [];
    const n = nums.length;
    
    for (let i = 0; i < n - 2; i++) {
        for (let j = i + 1; j < n - 1; j++) {
            for (let k = j + 1; k < n; k++) {
                if (nums[i] + nums[j] > nums[k]) {
                    result.push([nums[i], nums[j], nums[k]]);
                }
                // 剪枝
                if (nums[i] + nums[j] <= nums[k]) {
                    break;
                }
            }
        }
    }
    
    return result;
}

// 示例
const nums = [2, 2, 3, 4];
const triangles = validTriangles(nums);
console.log(triangles);

码小课提醒

以上代码给出了解决合法三角数问题的三种不同语言的实现方式。码小课网站中有更多关于算法和数据结构的内容分享，欢迎大家学习交流，共同进步。