Условие

Даны два массива aliceSizes и bobSizes, где элементы представляют размеры конфет у Алисы и Боба. Нужно найти такую пару (x, y), чтобы после обмена конфет их общие суммы стали равны. Если решений несколько, вернуть любое.

Примеры

Input: aliceSizes = [1, 1], bobSizes = [2, 2] Output: [1, 2]

Input: aliceSizes = [1, 2], bobSizes = [2, 3] Output: [1, 2]

Input: aliceSizes = [2], bobSizes = [1, 3] Output: [2, 3]

Решение

fun fairCandySwap(aliceSizes: IntArray, bobSizes: IntArray): IntArray {
    // Считаем сумму конфет у Алисы и Боба
    val sumAlice = aliceSizes.sum()
    val sumBob = bobSizes.sum()

    // Вычисляем разницу для обмена
    val delta = (sumAlice - sumBob) / 2

    // Преобразуем массив Боба в сет для быстрого поиска
    val bobSet = bobSizes.toSet()

    // Ищем подходящую пару
    for (x in aliceSizes) {
        val y = x - delta
        if (y in bobSet) {
            return intArrayOf(x, y)
        }
    }

    return intArrayOf() // Это место недостижимо, так как решение гарантировано
}

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

O(N + M), где N — длина aliceSizes, M — длина bobSizes.

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

O(M), где M — количество уникальных элементов в bobSizes.