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

Метод 1: подход грубой силы
Подход грубой силы включает проверку каждой пары чисел в массиве, чтобы увидеть, равна ли их сумма целевому значению. Хотя это решение имеет временную сложность O(n^2), его легко реализовать. Вот пример фрагмента кода:

fun twoSum(nums: IntArray, target: Int): IntArray {
    for (i in 0 until nums.size - 1) {
        for (j in i + 1 until nums.size) {
            if (nums[i] + nums[j] == target) {
                return intArrayOf(i, j)
            }
        }
    }
    throw IllegalArgumentException("No two numbers sum up to the target value.")
}

Метод 2: подход HashMap
Использование HashMap может значительно улучшить временную сложность до O(n) за счет обмена пространства на скорость. Мы можем перебирать массив, сохраняя дополнение каждого числа (цель минус текущий элемент) в качестве ключа и его индекс в качестве значения. Если мы встретим число, существующее в HashMap, это означает, что мы нашли пару, которая в сумме соответствует цели. Вот пример фрагмента кода:

fun twoSum(nums: IntArray, target: Int): IntArray {
    val map = HashMap<Int, Int>()
    for (i in nums.indices) {
        val complement = target - nums[i]
        if (map.containsKey(complement)) {
            return intArrayOf(map[complement]!!, i)
        }
        map[nums[i]] = i
    }
    throw IllegalArgumentException("No two numbers sum up to the target value.")
}

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

fun twoSum(nums: IntArray, target: Int): IntArray {
    val sortedNums = nums.sortedArray()
    var left = 0
    var right = sortedNums.size - 1
    while (left < right) {
        val sum = sortedNums[left] + sortedNums[right]
        when {
            sum == target -> return intArrayOf(nums.indexOf(sortedNums[left]), nums.lastIndexOf(sortedNums[right]))
            sum < target -> left++
            else -> right--
        }
    }
    throw IllegalArgumentException("No two numbers sum up to the target value.")
}

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