Bestimmen Sie in der angegebenen Liste von Ganzzahlen, nicht negativen Zahlen, ob die Liste ein Zahlenpaar enthält, sodass deren Summe dem angegebenen number entspricht. Wenn ja, geben Sie ihre Indizes in Form eines Paares von kleiner nach größer zurück. Wenn nicht, geben Sie Pair (-1, -1) zurück.

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)
}

Ich weiß, dass mein Code, abgesehen von der Tatsache, dass er nicht funktioniert, alles andere als perfekt ist. Und ich möchte die idiomatischste Lösung aus Sicht der Kotlin-Sprache erhalten.

-1
rost 19 Jän. 2019 im 09:11

3 Antworten

Beste Antwort

Dies ist buchstäblich eine der häufigsten Interviewfragen.

Ihre aktuelle Lösung hat eine zeitliche Komplexität von O (N ^ 2) , was nicht gut ist. Sie hat jedoch eine räumliche Komplexität von O (1) , was gut ist .

Hier ist eine funktionierende Version dieses Ansatzes:

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)
}

Nachdem Sie etwas Ähnliches wie oben codiert haben, werden Sie von Ihrem Interviewer höchstwahrscheinlich aufgefordert, die Zeitkomplexität auf O (N) zu optimieren (die Raumkomplexität muss auf O (N) erhöht werden aber das ist ok, zeitliche Komplexität ist in den meisten Fällen wichtiger).

Sie können dies tun, indem Sie einen Durchgang mit einem 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)
}

Hinweis: Bei den beiden oben genannten Lösungen werden zwei Annahmen getroffen: 1) Das Eingabearray ist nicht sortiert. 2) Wenn das Eingabearray mehr als ein gültiges Paar enthält, ist nur ein gültiges Paar in Ordnung.

3
shash678 20 Jän. 2019 im 22:21

Verwenden Sie 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
Willi Mentzel 19 Jän. 2019 im 06:48

(Mir ist nur klar, dass dies NICHT gültig ist. Bitte überspringen Sie diese Lösung :() Hier gibt es 2 Kommentare.

  1. Stellen Sie sich vor, number = -2 und list = listOf(-1). Dann kann Pair(-1, -1) uns nicht sagen, ob dieses Paar in out list verfügbar ist. Eine andere Sache ist, dass Kotlin keine Sicherheitsfunktion hat. Wir können es als nullbaren Typ zurückgeben, in diesem Fall Pair<Int, Int>?. Wenn unsere Funktion den Wert Null zurückgibt, bedeutet dies, dass es kein mögliches Paar gibt, nach dem wir explizit suchen.
  2. Meine alternative Lösung ist das Konzept der funktionalen Programmierung.
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 }
}

Fühlen Sie sich frei, um Diskussion zu haben :)

-1
MyrmidonXIIV 19 Jän. 2019 im 06:58