Поиск двух чисел с заданной суммой

Решение: Поиск двух чисел с заданной суммой

Анализ задачи

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

Решение: Оптимальный алгоритм O(n) с HashMap

Лучший подход использует HashMap для решения в одну итерацию:

fun findTwoSum(nums: IntArray, target: Int): Pair<Int, Int>? {
    val seen = mutableMapOf<Int, Int>()  // value -> index
    
    for (i in nums.indices) {
        val complement = target - nums[i]  // какое число нам нужно
        
        // Если нужное число уже видели - нашли пару
        if (seen.containsKey(complement)) {
            return Pair(seen[complement]!!, i)
        }
        
        // Сохраняем текущий элемент в карту
        seen[nums[i]] = i
    }
    
    return null  // Пара не найдена
}

Как это работает

Пример 1: findTwoSum([2, 7, 11, 15], 9)

Итерация 0:
  nums[0] = 2
  complement = 9 - 2 = 7
  seen.containsKey(7)? Нет
  seen = {2 -> 0}

Итерация 1:
  nums[1] = 7
  complement = 9 - 7 = 2
  seen.containsKey(2)? ДА! seen[2] = 0
  Возвращаем Pair(0, 1) ✓

Пример 2: findTwoSum([3, 2, 4], 6)

Итерация 0:
  nums[0] = 3, complement = 3, seen = {3 -> 0}
Итерация 1:
  nums[1] = 2, complement = 4, seen = {3 -> 0, 2 -> 1}
Итерация 2:
  nums[2] = 4, complement = 2, seen.containsKey(2)? ДА! seen[2] = 1
  Возвращаем Pair(1, 2) ✓

Сложность

• Time: O(n) - одна итерация по массиву
• Space: O(n) - HashMap может содержать все элементы

Edge Cases

// 1. Два одинаковых элемента
findTwoSum(intArrayOf(3, 3), 6)
// → Pair(0, 1) - разные индексы ✓

// 2. Элемент сам по себе половина суммы
findTwoSum(intArrayOf(5, 5, 7), 10)
// → Pair(0, 1) - находит два 5 с разными индексами ✓

// 3. Пустой массив
findTwoSum(intArrayOf(), 10)
// → null ✓

// 4. Один элемент
findTwoSum(intArrayOf(5), 10)
// → null - нечего складывать ✓

// 5. Нет решения
findTwoSum(intArrayOf(1, 2, 3), 10)
// → null ✓

// 6. Отрицательные числа
findTwoSum(intArrayOf(-1, -2, 5, 8), 3)
// → Pair(2, 3) для -2 + 5 = 3 ✓

// 7. Нулевые значения
findTwoSum(intArrayOf(0, 0, 1), 0)
// → Pair(0, 1) ✓

Версия с документацией

/**
 * Находит два числа в массиве, сумма которых равна целевому значению.
 * 
 * @param nums Массив целых чисел
 * @param target Целевое значение суммы
 * @return Pair(index1, index2) где index1 < index2, или null если решения нет
 * 
 * Сложность: O(n) время, O(n) память
 * 
 * Примеры:
 * - findTwoSum([2, 7, 11, 15], 9) -> Pair(0, 1)
 * - findTwoSum([3, 2, 4], 6) -> Pair(1, 2)
 * - findTwoSum([1, 2], 10) -> null
 */
fun findTwoSum(nums: IntArray, target: Int): Pair<Int, Int>? {
    val seen = mutableMapOf<Int, Int>()
    
    for (i in nums.indices) {
        val complement = target - nums[i]
        
        seen[complement]?.let { complementIndex ->
            return Pair(complementIndex, i)
        }
        
        seen[nums[i]] = i
    }
    
    return null
}

Альтернатива с Sequence (функциональный стиль)

fun findTwoSum(nums: IntArray, target: Int): Pair<Int, Int>? {
    val indexed = nums.withIndex()
    
    return indexed.firstOrNull { (i, num) ->
        val complement = target - num
        indexed.any { (j, other) -> j != i && other == complement && j > i }
    }?.let { (i, _) ->
        val complement = target - nums[i]
        indexed.firstOrNull { (j, other) -> j != i && other == complement && j > i }
            ?.let { (j, _) -> Pair(i, j) }
    }
}

Этот подход менее эффективный (O(n^2)), но показывает функциональный стиль Kotlin.

Наивное решение O(n²) для сравнения

fun findTwoSumBrute(nums: IntArray, target: Int): Pair<Int, Int>? {
    for (i in nums.indices) {
        for (j in i + 1 until nums.size) {
            if (nums[i] + nums[j] == target) {
                return Pair(i, j)
            }
        }
    }
    return null
}

Недостатки:

• Вложенные циклы - медленнее при больших массивах
• Для массива из 1млн элементов будет выполняться 10^12 операций
• Может быть неприемлемо для мобильного приложения

Unit Tests

class FindTwoSumTest {
    
    @Test
    fun testBasicCase() {
        val result = findTwoSum(intArrayOf(2, 7, 11, 15), 9)
        assertEquals(Pair(0, 1), result)
    }
    
    @Test
    fun testDifferentOrder() {
        val result = findTwoSum(intArrayOf(3, 2, 4), 6)
        assertEquals(Pair(1, 2), result)
    }
    
    @Test
    fun testDuplicates() {
        val result = findTwoSum(intArrayOf(3, 3), 6)
        assertEquals(Pair(0, 1), result)
    }
    
    @Test
    fun testNoSolution() {
        val result = findTwoSum(intArrayOf(1, 2, 3), 10)
        assertNull(result)
    }
    
    @Test
    fun testEmptyArray() {
        val result = findTwoSum(intArrayOf(), 5)
        assertNull(result)
    }
    
    @Test
    fun testSingleElement() {
        val result = findTwoSum(intArrayOf(5), 10)
        assertNull(result)
    }
    
    @Test
    fun testNegativeNumbers() {
        val result = findTwoSum(intArrayOf(-1, -2, 5, 8), 3)
        assertEquals(Pair(2, 3), result)
    }
    
    @Test
    fun testZeroValues() {
        val result = findTwoSum(intArrayOf(0, 0, 1), 0)
        assertEquals(Pair(0, 1), result)
    }
}

Почему HashMap вместо других структур

Для большинства случаев HashMap оптимален.

Вывод

Оптимальное решение:

• HashMap подход O(n) - выбираем для продакшена
• Простота кода + высокая производительность
• Хорошая читаемость
• Проходит все edge cases
• Подходит для высоконагруженных систем (как мобильное приложение)