Количество треугольников

Постановка задачи

nums = [2, 2, 3, 4]

3

[2, 3, 4] (используем первую двойку)
[2, 3, 4] (используем вторую двойку)
[2, 2, 3]

nums = [4, 2, 3, 4]

4

Решение

На первый взгляд задача выглядит как простой перебор всех троек. Можно использовать три вложенных цикла, проверить каждую комбинацию сторон и посчитать подходящие треугольники. Такое решение будет работать за O(n³).

При n = 1000 это уже слишком много: количество троек будет порядка миллиарда. На интервью такой подход можно предложить как стартовый, но нужно сразу перейти к оптимизации.

Главное наблюдение здесь связано с неравенством треугольника. Для того, чтобы из трех отрезков a, b и c мы могли составить треугольник, должны выполняться условия:

a + b > c
a + c > b
b + c > a

Например из сторон a = 5, b = 4, c = 8 можно составить треугольник, так как выполняется неравенство треугольника:

5 + 4 > 8
5 + 8 > 4
4 + 8 > 5

Из сторон a = 5, b = 3, c = 8 треугольник составить нельзя, так как нарушается одно из условий:

5 + 3 > 8 - ложно
5 + 8 > 3
3 + 8 > 5

Заметим, что если отсортировать стороны так, что a <= b <= c, то достаточно проверить только одно условие:

a + b > c

Остальные два условия выполняются автоматически, потому что c - самая длинная сторона.

Идея решения:

Сначала сортируем массив. После этого будем фиксировать самую длинную сторону треугольника c и искать для нее пары меньших сторон a и b.

Пусть k - индекс самой длинной стороны. Тогда все возможные стороны a и b лежат левее k, потому что массив отсортирован.

Для каждого k ставим два указателя:

• l в начало массива
• r прямо перед k

Теперь проверяем сумму nums[l] + nums[r].

Если nums[l] + nums[r] > nums[k], значит, треугольник корректен. Более того, все элементы между l и r тоже подойдут в качестве левой стороны вместе с nums[r] и nums[k].

Почему? Потому что массив отсортирован. Если самый маленький кандидат nums[l] уже дает корректный треугольник с nums[r], то любой элемент правее l будет не меньше и тоже даст корректный треугольник.

Значит, мы можем добавить к ответу сразу r - l треугольников и сдвинуть r влево, чтобы попробовать следующую сторону b.

Если же nums[l] + nums[r] <= nums[k], текущая сумма слишком маленькая. Сдвигать r влево бессмысленно, потому что сумма станет только меньше. Поэтому нужно увеличить левую сторону и сдвинуть l вправо.

В этом и заключается паттерн двух указателей: после сортировки мы не перебираем все пары заново, а используем монотонность массива, чтобы сдвигать ровно тот указатель, который может улучшить ситуацию.

Основные шаги:

1. Сортируем массив nums по неубыванию.

2. Фиксируем самую длинную сторону nums[k].

   • Идем индексом k справа налево, начиная с конца массива.
   • Для каждого k рассматриваем только элементы левее него.

3. Запускаем два указателя внутри левой части массива.

   • l = 0
   • r = k - 1

4. В цикле: пока l < r.

   • Если nums[l] + nums[r] > nums[k], добавляем r - l к ответу и сдвигаем r влево.
   • Иначе сдвигаем l вправо.

5. Завершение цикла:

   • Когда указатели встретились, все пары для текущего k обработаны.
   • Переходим к следующему k.

Разберем пример:

nums = [2, 2, 3, 4]

Массив уже отсортирован.

1. Фиксируем k = 3, то есть nums[k] = 4.

   • l = 0, r = 2
   • Проверяем nums[l] + nums[r] > nums[k]: 2 + 3 > 4
   • Условие выполняется, значит, все элементы от l до r - 1 подходят вместе с nums[r] и nums[k].
   • Добавляем r - l = 2 треугольника.
   • Это тройки [2, 3, 4] и [2, 3, 4] с разными индексами.
   • Сдвигаем r: стало 1.

2. Продолжаем для k = 3.

   • l = 0, r = 1
   • Проверяем 2 + 2 > 4
   • Условие не выполняется.
   • Сдвигаем l: стало 1.
   • Указатели встретились, переходим к следующему k.

3. Фиксируем k = 2, то есть nums[k] = 3.

   • l = 0, r = 1
   • Проверяем 2 + 2 > 3
   • Условие выполняется.
   • Добавляем r - l = 1 треугольник.
   • Это тройка [2, 2, 3].
   • Сдвигаем r: стало 0.

4. Завершение.

   • Всего получили 3 корректных треугольника.

Итог: ответ равен 3.

Оценка сложности

Временная сложность

Сначала мы сортируем массив за O(n log n). Затем для каждого фиксированного индекса k запускаем два указателя, которые вместе проходят левую часть массива за линейное время.

В сумме вложенный проход дает O(n²), поэтому итоговая временная сложность равна O(n²).

Пространственная сложность

Мы не создаем дополнительных структур данных для подсчета ответа. Если не учитывать память, которую может использовать встроенная сортировка, получаем O(1).

Код решения

Приведем код решения.

import "sort"
 
func triangleNumber(nums []int) int {
    sort.Ints(nums)
    n := len(nums)
    count := 0
    for k := n - 1; k >= 2; k-- {
        l := 0
        r := k - 1
        for l < r {
            if nums[l] + nums[r] > nums[k] {
                count += r - l
                r--
            } else {
                l++
            }
        }
    }
    return count
}

Итоги

Вот основные итоги по задаче:

1. Сортировка упрощает проверку. После сортировки достаточно проверить только nums[l] + nums[r] > nums[k], где nums[k] - самая длинная сторона.

2. Два указателя убирают лишний перебор. Вместо проверки всех пар для каждого k мы двигаем l и r навстречу друг другу.

3. Главный момент алгоритма. Когда nums[l] + nums[r] > nums[k], можно добавить сразу r - l треугольников, потому что все элементы между l и r тоже достаточно большие.

4. Граничные случаи. Нули не требуют отдельной обработки. После сортировки они просто не пройдут проверку a + b > c, если не могут быть стороной корректного треугольника.