Задача: №16. 3Sum Closest #medium

Условие:

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

Решение:

class Solution {
    fun threeSumClosest(nums: IntArray, target: Int): Int {
        Arrays.sort(nums)
        var numsLen = nums.size
        var lastTwoSum = nums[numsLen - 1] + nums[numsLen - 2]
        var result = 0
        var distance = Integer.MAX_VALUE

        if (nums[0] + nums[1] + nums[2] > target)  return nums[0] + nums[1] + nums[2]
        if (lastTwoSum + nums[numsLen - 3] < target)  return lastTwoSum + nums[numsLen - 3]
        if (nums[0] == nums[numsLen - 1])  return 3 * nums[0]

        for (i in 0..(numsLen - 3)) {
            var cur0 = nums[i]
            if (i == 0 || cur0 != nums[i-1]) { 
                if (cur0 + nums[i + 1] + nums[i + 2] > target) {
                    if (cur0 + nums[i + 1] + nums[i + 2] - target < distance)  
                        result = cur0 + nums[i + 1] + nums[i + 2]
                    break
                }
                if (cur0 + lastTwoSum <= target) {  
                    if (target - cur0 + lastTwoSum < distance) {
                        distance = target - cur0 + lastTwoSum
                        result = cur0 + lastTwoSum
                    }
                    continue
                }
                var left = i + 1
                var right = numsLen - 1
                while (left < right) {
                    var sum = cur0 + nums[left] + nums[right]
                    if (sum == target)  return target
                    if (Math.abs(target - sum) < distance) {
                        distance = Math.abs(target - sum)
                        result = sum
                    }
                    if (sum > target)
                        right--
                    else
                        left++
                }
            }
        }
        return result
    }
}

Пояснение:
Сортировка: Сначала массив nums сортируется для упрощения поиска.
Инициализация переменных: Определяются переменные для хранения длины массива, суммы последних двух элементов и начального значения результата.
Основной цикл: Проходит по каждому элементу массива, рассматривая его как первый элемент тройки.
Двухуказательный метод: Использует два указателя для поиска двух других элементов массива, которые вместе с текущим элементом дадут сумму, наиболее близкую к target.
Проверка и обновление результата: Сравнивает текущую сумму с целевым значением и обновляет результат, если находится более близкая сумма.
Возврат результата: Функция возвращает сумму, которая является наилучшей суммой тройки элементов, наиболее близкой к целевому значению.

Задача: №17. Letter Combinations of a Phone Number #medium

Условие:

Учитывая строку, содержащую цифры от 2 до 9 включительно, верните все возможные комбинации букв, которые может представлять число. Верните ответ в любом порядке. Соответствие цифр буквам (как на кнопках телефона) приведено ниже. Обратите внимание, что 1 не соответствует никаким буквам.

Решение:

class Solution {
    
    fun letterCombinations(digits: String): List<String> =
        digits.takeIf { it.isNotEmpty() }?.fold(listOf("")) { acc, c ->
            c.letters.flatMap { letter -> acc.map { it + letter } }
        } ?: emptyList()

    private val Char.letters get() = when(this) {
        '2' -> listOf('a', 'b', 'c')
        '3' -> listOf('d', 'e', 'f')
        '4' -> listOf('g', 'h', 'i')
        '5' -> listOf('j', 'k', 'l')
        '6' -> listOf('m', 'n', 'o')
        '7' -> listOf('p', 'q', 'r', 's')
        '8' -> listOf('t', 'u', 'v')
        '9' -> listOf('w', 'x', 'y', 'z')
        else -> listOf()
    }
}

Пояснение:
Проверка пустого ввода: Если входная строка digits пуста, функция возвращает пустой список, так как нет цифр для обработки.

Формирование комбинаций:

Используется метод fold для последовательного обработки каждого символа строки digits. На начальном этапе в аккумулятор передается список, содержащий пустую строку.
Для каждого символа c в digits, получаются возможные буквы, соответствующие этому символу (c.letters).
Далее, для каждой буквы из возможных (letter), происходит объединение этой буквы со всеми строками в текущем аккумуляторе (acc), формируя новые строки. Результат каждого шага объединяется в список, что позволяет формировать все возможные комбинации.
Получение букв по цифре: Метод расширения letters для типа Char возвращает список букв, соответствующих данной цифре. Это позволяет быстро и удобно получить доступ к возможным буквам для каждой цифры в строке.

Задача: №18. 4Sum #medium

Условие:

Учитывая массив nums из n целых чисел, верните массив всех уникальных четверок [nums[a], nums[b], nums[c], nums[d]] таких, что:
0 <= a, b, c, d < n
a, b, c и d различны.
nums[a] + nums[b] + nums[c] + nums[d] == цель
Вы можете вернуть ответ в любом порядке

Решение:

class Solution {
    fun fourSum(nums: IntArray, target: Int): List<List<Int>> {
        nums.sort()
        val target: Long = target.toLong()
        val sums = mutableListOf<List<Int>>()
        val lastIndex = nums.size - 1

        for (i in 0..lastIndex - 3) {
            if (i > 0 && nums[i - 1] == nums[i]) continue

            val targetI = target - nums[i]

            if (targetI < nums[i].toLong() + nums[i + 1].toLong() + nums[i + 2].toLong()) break
            if (targetI > nums[lastIndex].toLong() + nums[lastIndex - 1].toLong() + nums[lastIndex - 2].toLong()) {
                continue
            }

            for (j in i + 1..lastIndex - 2) {
                if (j > i + 1 && nums[j - 1] == nums[j]) continue

                val targetJ = targetI - nums[j]

                if (targetJ < nums[j].toLong() + nums[j + 1].toLong()) break
                if (targetJ > nums[lastIndex].toLong() + nums[lastIndex - 1].toLong()) continue

                for (k in j + 1..lastIndex - 1) {
                    if (k > j + 1 && nums[k - 1] == nums[k]) continue

                    val targetK = targetJ - nums[k]
                    val l = nums.binarySearch(targetK.toInt(), fromIndex = k + 1)
                    if (l >= 0) {
                        sums.add(listOf(nums[i], nums[j], nums[k], nums[l]))
                    }
                }
            }
        }

        return sums
    }
}

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

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

Первые вложенные циклы:

Внешний цикл (i) проходит по каждому элементу массива, рассматривая его как первый элемент возможной комбинации.
На каждом шаге проверяется, не был ли предыдущий элемент уже рассмотрен (if (i > 0 && nums[i - 1] == nums[i])), чтобы избежать дублирующихся комбинаций.
Определение целевой суммы для оставшихся элементов:

Рассчитывается targetI, которое представляет собой разницу между общим target и текущим элементом массива nums[i].
Второй вложенный цикл:

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

Рассчитывается targetJ, которое представляет собой разницу между targetI и текущим элементом nums[j].
Третий вложенный цикл:

Третий цикл (k) проходит по оставшимся элементам после j для нахождения третьего элемента комбинации.
Проверяется, не был ли предыдущий элемент уже рассмотрен.
Бинарный поиск:

Для поиска четвертого элемента используется метод binarySearch, что позволяет эффективно находить элемент, сумма с предыдущими тремя элементами которого равна target.
Если элемент найден (l >= 0), добавляется текущая комбинация четырех элементов в список sums.
Возвращение результата:

После завершения всех циклов, список sums содержит все уникальные комбинации четырех элементов, сумма которых равна target. Этот список возвращается в качестве результата.