Как суммировать элементы списка каждый с каждым?
В заданном списке целых неотрицательных чисел определить, есть ли в списке такие пары чисел, что их сумма равна заданному number.
Если да, верните их индексы в виде Pair от меньшего к большему.
Если нет, верните 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)
}
Я знаю, что помимо того, что мой код не работает, он еще далек от совершенства. И хотелось бы получить максимально идиоматичное решение с точки зрения языка Котлин.
Я поставил этот, потому что многие Java-разработчики очень хорошо знают Kotlin и могут помочь
если они хорошо знают Kotlin, они также будут следить за тегом Kotlin.
Ответы 3
(Я просто понимаю, что это НЕдействительно. Поэтому, пожалуйста, пропустите это решение :() Здесь есть 2 комментария.
- Представьте, если
number = -2иlist = listOf(-1). ТогдаPair(-1, -1)не может нам сказать, доступна ли эта пара на выходеlist. Другое дело, что в Kotlin отсутствует функция безопасности. Мы можем вернуть его как тип, допускающий значение NULL, в данном случаеPair<Int, Int>?. Если наша функция возвращает нулевое значение, это означает, что нет возможных пар, которые мы ищем явно. - Мое альтернативное решение связано с концепцией функционального программирования.
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 }
}
Не стесняйтесь обсуждать :)
Мне жаль. Забыл добавить условие, что в списке только положительные числа. Уже отредактировал вопрос.
Поскольку вам нужна только одна пара индексов, сумма элементов которых равна определенному числу, используйте 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)
}
@ А.Рост, что ты имеешь в виду? Если список пуст, будет возвращено (-1, -1).
assertEquals( Pair(-1, -1), findSumOfTwo(emptyList(), 1) ) Этот тест JUnit не выполнен с фактическим результатом (2, 2) вместо (-1, -1)
@ А.Рост, это невозможно. если список пуст, цикл никогда не запустится... в результате будет возвращена пара (-1, -1). убедитесь сами: pl.kotl.in/rysVn2bmE
Хм, ты прав. Очень странно, что моя JIdea выдает ошибку.
Я нахожу ошибку. Это не работает с assertEquals( Pair(-1, -1), findSumOfTwo(listOf(1, 2, 3), 6). Прошу прощения, что ввел в заблуждение пустым списком
@A.Rost результат findSumOfTwo(listOf(1, 2, 3), 6) равен (2, 2), что является индексом 3, поэтому правильно, если на одно и то же число можно ссылаться дважды. Если вы не хотите, чтобы выражение if выглядело так, if (e1 + e2 == число && i1 != i2), так что никаких больших изменений. посмотрите, насколько он краток и лаконичен.
Это буквально один из самых распространенных вопросов на собеседовании.
Ваше текущее решение имеет временную сложность О (Н ^ 2), что не очень хорошо, однако имеет пространственную сложность О(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)
}
После написания кода, подобного приведенному выше, ваш интервьюер, скорее всего, попросит вас оптимизировать временную сложность до НА) (пространственная сложность должна быть увеличена до НА), но это нормально, временная сложность важнее в большинстве случаев).
Вы можете сделать это, используя один проход, используя 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) Если во входном массиве есть более одной допустимой пары, возвращается только одна допустимая пара.
если вам не нужно решение Java, удалите этот тег