Условие

Дан массив целых чисел nums. Требуется вернуть наибольший периметр треугольника с ненулевой площадью, который можно составить из трех элементов этого массива. Если невозможно составить такой треугольник, верните 0.

Примеры

Input: nums = [2,1,2] Output: 5 Explanation: Треугольник со сторонами 2, 1 и 2 имеет периметр 5.

Input: nums = [1,2,1,10] Output: 0 Explanation:

Вы не можете использовать длины сторон 1, 1 и 2 для формирования треугольника.

Вы не можете использовать длины сторон 1, 1 и 10 для формирования треугольника.

Вы не можете использовать длины сторон 1, 2 и 10 для формирования треугольника.

Поскольку невозможно использовать любые три длины сторон для формирования треугольника с ненулевой площадью, мы возвращаем 0.

Решение

fun largestPerimeter(nums: IntArray): Int {
    // Сортировка массива по возрастанию с использованием пузырьковой сортировки
    for (i in nums.indices) {
        for (j in 0 until nums.size - i - 1) {
            if (nums[j] > nums[j + 1]) {
                val temp = nums[j]
                nums[j] = nums[j + 1]
                nums[j + 1] = temp
            }
        }
    }

    // Проходим по массиву с конца к началу
    for (i in nums.size - 3 downTo 0) {
        // Проверяем условие существования треугольника
        if (nums[i] + nums[i + 1] > nums[i + 2]) {
            // Возвращаем периметр треугольника
            return nums[i] + nums[i + 1] + nums[i + 2]
        }
    }

    // Если не удалось найти подходящие стороны, возвращаем 0
    return 0
}

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

O(n log n), где n — длина массива nums, из-за сортировки массива.

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

O(1), так как используется постоянное количество дополнительной памяти.