Как суммировать элементы списка каждый с каждым?

Question

В указанном списке целых чисел, неотрицательных чисел, определите, есть ли в списке пара чисел, чтобы их сумма равнялась указанной number.Если да, вернуть их индексы в виде пары от меньшего к большему.Если нет, верните Pair (-1, -1).

fun findSumOfTwo(list: List<Int>, number: Int): Pair<Int, Int> {
    for (item in list) {
        for (digit in list - 1) {
            if (item + digit == number) return Pair (list[item], list [digit])
        }
    }
    return Pair (-1, -1)
}

Я знаю, что, кроме того, что мой код не работает, он далек от совершенства.И я хотел бы получить наиболее идиоматическое решение с точки зрения языка Kotlin.

Answer 1

Поскольку вам нужна только одна пара индексов, у которых сумма элемента равна определенному числу, используйте forEachIndexed :

fun findSumOfTwo(list: List<Int>, number: Int): Pair<Int, Int> {

   list.forEachIndexed { i1, e1 ->
        list.forEachIndexed { i2, e2 ->
            if(e1 + e2 == number) {
                return i1 to i2
            }
        }
    }

    return Pair (-1, -1)
}

Answer 2

Это буквально один из самых распространенных вопросов интервью.

Ваше текущее решение имеет временную сложность O (N ^ 2) , что не хорошо, однако его пространственная сложность составляет O (1) , что хорошо.

Вот рабочая версия этого подхода:

fun findSumOfTwo(arr: IntArray, targetSum: Int): Pair<Int, Int> {
    if (arr.size < 2) return Pair(-1, -1)
    var sum: Int
    for (i in 0..arr.size - 2) {
        for (j in i + 1..arr.size - 1) {
            sum = arr[i] + arr[j]
            if (sum == targetSum)  {
                if (arr[i] < arr[j]) {
                    return Pair(i, j)
                }
                return Pair(j, i)
            }
        }
    }
    return Pair(-1, -1)
}

После кодирования чего-то похожего выше ваш интервьюер, скорее всего, попросит вас оптимизировать временную сложность до O (N) , (сложность пространства должна увеличиться до O (N) но это нормально, сложность времени важнее в большинстве случаев).

Вы можете сделать это, используя один проход, используя HashMap :

fun findSumOfTwo(arr: IntArray, targetSum: Int): Pair<Int, Int> {
    if (arr.size < 2) return Pair(-1, -1)
    var map = HashMap<Int, Int>()
    for (i in 0..arr.size - 1) {
        var complement = targetSum - arr[i]
        if (map.containsKey(complement)) {
            var complementIndex = map.get(complement)!!
            if (arr[i] < complement) {
                return Pair(i, complementIndex)
            }
            return Pair(complementIndex, i)
        }
        map.put(arr[i], i)
    }
    return Pair(-1, -1)
}

Примечание: два приведенных выше решения основаны на двух допущениях: 1) входной массив не отсортирован. 2) Если во входном массиве более одной действительной пары, возвращающей только одну действительную пару, то все в порядке.

Answer 3

(я просто понимаю, что это НЕ верно. Поэтому, пожалуйста, пропустите это решение :(). Здесь 2 комментария.

1. Представь, если number = -2 и list = listOf(-1). Тогда Pair(-1, -1) не может сказать нам, доступна ли эта пара в list. Другое дело, что у Котлина появляется нулевая функция безопасности. Мы можем вернуть его как обнуляемый тип, в данном случае Pair<Int, Int>?. Если наша функция возвращает нулевое значение, это означает, что нет возможных пар, которые мы ищем явно.
2. Мое альтернативное решение поставляется с концепцией функционального программирования.

fun findSumOfTwo(list: List<Int>, number: Int): Pair<Int, Int>? {
    return list
            .flatMap { it1 -> list.map { it2 -> Pair(it1, it2) } }
            .firstOrNull { it.first + it.second == number }
}

Не стесняйтесь обсуждать:)