Задача: 611. Valid Triangle Number
Сложность: medium

Если задан целочисленный массив nums, верните количество выбранных из массива троек, которые могут образовывать треугольники, если принять их за длины сторон треугольника.

Пример:

Input: nums = [2,2,3,4]
Output: 3

👨‍💻 Алгоритм:

1⃣Отсортируйте массив nums.

2⃣Используйте три вложенных цикла: для каждого фиксированного третьего элемента, используйте два указателя для поиска подходящих первых двух элементов, которые удовлетворяют неравенству треугольника.

3⃣Увеличивайте счетчик на количество подходящих пар для каждого третьего элемента.

😎 Решение:

function triangleNumber($nums) {
    sort($nums);
    $n = count($nums);
    $count = 0;
    
    for ($k = $n - 1; $k >= 2; $k--) {
        $i = 0;
        $j = $k - 1;
        while ($i < $j) {
            if ($nums[$i] + $nums[$j] > $nums[$k]) {
                $count += $j - $i;
                $j--;
            } else {
                $i++;
            }
        }
    }
    
    return $count;
}

Ставь 👍 и забирай 📚 Базу знаний