Решение TwoSum Swift

Question

Я только начал изучать кодирование с помощью swift и пробовал TwoSum.

"Учитывая массив целых чисел, вернуть индексы двух чисел так, чтобы они складывались до определенной цели.

Вы можете предположить, что каждый вход будет иметь ровно одно решение, и вы можетене используйте один и тот же элемент дважды.

Пример:

При заданных числах = [2, 7, 11, 15], target = 9,

Поскольку числа [0] +nums [1] = 2 + 7 = 9, вернуть [0, 1]. "

Я нашел некоторые решения от GitHub, которые я не могу понять.

код от https://github.com/soapyigu/LeetCode-Swift/blob/master/Array/TwoSum.swift

class TwoSum {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var dict = [Int: Int]()

        for (i, num) in nums.enumerated() {
            if let lastIndex = dict[target - num] {
                return [lastIndex, i]
            }
            dict[num] = i
        }
        fatalError("No valid outputs")
    }
}

Может ли кто-нибудь так любезно объяснить кодам.Большое спасибо.

Answer 1

В превосходном ответе Sweeper он объяснил, для чего используется dict: он позволяет использовать значение из массива для поиска индекса этого значения.Было бы более очевидно, для чего использовался словарь, если бы мы назвали его indexes, и этот код создает тот же словарь более явным образом:

var indexes = [Int: Int]()

for index in 0..<array.count {
    let value = array[index]
    indexes[value] = index
}

После этого вы получаете словарь:

[2:0, 7:1, 11:2, 15:3]

Вы могли бы написать функцию следующим образом:

func twoSum(_ array: [Int], _ target: Int) -> [Int] {
    var indexes = [Int: Int]()

    for index in 0..<array.count {
        let value = array[index]
        indexes[value] = index
    }

    for index in 0..<array.count {
        let value = array[index]
        if let otherIndex = indexes[target - value],
           index != otherIndex {
            return [index, otherIndex]
        }
    }
    fatalError("Unable to match values")
}

Это гораздо более многогранный (и менее эффективный) способ сделать то же самое.Он проходит по массиву дважды, а не один раз, но результаты должны быть одинаковыми.

Answer 2

Учитывая массив целых чисел, вернуть индексы из двух чисел, так что они складываются до определенной цели.

var arr:[Int] = []
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    var toggle = false
    for i in 0..<nums.count {
        for j in i+1..<nums.count {
            if toggle == false {
                if(nums[i]+nums[j]==target){
                    toggle = true
                    arr.insert(i, at: 0)
                    arr.insert(j, at: 1)
                    break
                }
            }
        }
    }
    return arr
}

Пример:

Данные числа= [2, 7, 11, 15], target = 9,

Поскольку nums [0] + nums [1] = 2 + 7 = 9, вернуть [0, 1].

Answer 3

Инициализированный в методе dict сохраняет числа на входе в качестве ключей, а их индексы - в качестве значений.Программа использует это, чтобы запомнить, какой номер где.dict может сообщать вам такие вещи, как «число 2 с индексом 0».

Для каждого числа num с индексом i во входном массиве мы вычитаем num из target чтобы найти другой номер, который нам нужен, чтобы они суммировали до target.

Теперь у нас есть другой номер, который нам нужен, мы проверяем, видели ли мы такой номер раньше,путем поиска dict.Это то, что делает часть if let lastIndex = dict[target - num].Если dict знает, по какому индексу находится другое число, мы возвращаем этот индекс и i.

Если мы не видели этого числа раньше, мы записываем i в словарь подключ num, надеясь, что на более поздних итерациях мы сможем найти число, которое при добавлении к num составляет 9.