描述
给定一个整数数组,在该数组中,寻找三个数,分别代表三角形三条边的长度,问,可以寻找到多少组这样的三个数来组成三角形?
样例
样例 1:
输入: [3, 4, 6, 7]
输出: 3
解释:
可以组成的是 (3, 4, 6), (3, 6, 7), (4, 6, 7)
样例 2:
输入: [4, 4, 4, 4]
输出: 4
function action(array $arr) { $num = 0; $len = count($arr); if ($len < 3) return 0; // 先从大到小排序 rsort($arr, SORT_NUMERIC); for ( $i = 0; $i < $len - 2; $i++ ) { for ( $j = $i + 1; $j < $len - 1; $j++ ) { for ( $k = $j + 1; $k < $len; $k++ ) { // 三角形任意两边之和必须大于第三边, 也就是说 // 只要满足: 三角形的最长边 < 两条短边之和 即可 if ($arr[$i] < $arr[$j] + $arr[$k]) $num++; } } } return $num; }
/** * 三角形判断: * 最长的一条边大于其他两边即可 */ function triangleJudgment($arr) { // 初始化总个数 $number = 0; $length = count($arr); for ($x = 0; $x < $length; $x++) { for ($y = $x + 1; $y < $length; $y++) { for ($z = $y + 1; $z < $length; $z++) { $triangle = [$arr[$x], $arr[$y], $arr[$z]]; $max = max($triangle); // 最大的边 $sum = array_sum($triangle); // 三角形的边长总和 if ($max < $sum - $max) { $number++; } } } } return $number; }
/** * 根据数组,得出三角形组 * 给定一个整数数组,在该数组中,寻找三个数,分别代表三角形三条边的长度,问,可以寻找到多少组这样的三个数来组成三角形? */ public function actionSan($arr=[4,4,4,4]){ $i = 0; foreach ($arr as $key =>$value){ unset($arr[$key]); //删除第一条边 $arr1 = $arr; foreach ($arr1 as $key1 =>$value1){ unset($arr1[$key1]); //删除第二条边 $arr2 = $arr1; foreach ($arr2 as $key2 =>$value2){ if(($value+$value1)>$value2 || ($value==$value1&&$value==$value2)){ //两边之后大于第三边 或者 三边都相等 $i++; echo "(".$value.",".$value1.",".$value2.")";echo "<br>"; } } } } }