Программирование

Задачи с собеседований: Leetcode — Сумма двух

Опубликовано

3 года назад

07.10.2022

Автор:

AppTractor

Задача

Дан массив целых чисел nums и целое число target, нужно вернуть индексы двух чисел из массива, которые в сумме образуют target.

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

Вы можете вернуть ответ в любом порядке.

Сумма двух на Leetcode: https://leetcode.com/problems/two-sum/

Решение

Первое приходящее на ум решение — сделать два вложенных цикла, в которых перебирать массив, поочередно складывая числа и сравнивая получившееся с целевым значением.

Вот мое решение:

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {    

       var resultA = [Int]()

       outerLoop: for i in 0...nums.count - 2 {
            for j in (i+1)...nums.count - 1 {
                // Поиск суммы
                if ((nums[i] + nums[j]) == target) {

                    resultA.append(i)
                    resultA.append(j)

                    break outerLoop
                }
            }
        }               
        return resultA
    }
}

​x
 
class Solution {    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {    ​       var resultA = [Int]()​       outerLoop: for i in 0...nums.count - 2 {            for j in (i+1)...nums.count - 1 {                // Поиск суммы                if ((nums[i] + nums[j]) == target) {​                    resultA.append(i)                    resultA.append(j)​                    break outerLoop                }            }        }                       return resultA    }}

Лучший результат на Leetcode:

Время выполнения: 77 мс
Скорость выполнения — лучше 66.47% всех решений
Потребление памяти — лучше 90.65% решений.

Неплохо, но, очевидно, по скорости где то есть возможности для улучшения.

Что интересного из решения я узнал:

Break не выходит сразу из всех циклов, нужно определять внешний и из него выходить.
Можно оптимизировать перебор хотя бы на 2 элемента, чего многие (судя по показателям) не делают даже в этом подходе.
На самом деле результат Leetcode — плавающий и зависит от каких-то внутренних факторов. В следующий раз может быть другое время выполнения и другое потребление памяти, так что, наверное, стоит даже с одним и тем же кодом сделать несколько подходов в оценке.

Другое решение

Очевидно, судя по материкам решения, существует другой подход. Честное гугление показало, что можно сделать так:

Сначала хэшировать весь массив, определив позиции для каждого числа.
Потом один раз перебрать массив, ища в хэшированном массиве разницу между текущим элементом и target.

В качестве структуры хеша я использовал словарь (Dictionary). В нем для каждого элемента определяется его позиция в исходном массиве:

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {

        var resultA = [Int]()
        var numsVoc = [Int: Int]()

        for i in 0...nums.count - 1 {

            // Основное отличие. создаем словарь вида [Int: Int] = [Число: Его позиция в массиве]
            numsVoc[nums[i]] = i
        }    

        for i in 0...nums.count - 2 {
            // Поиск в словаре разницы
            if (numsVoc[target - nums[i]] != nil && numsVoc[target - nums[i]] != i) {

                resultA.append(i)
                resultA.append(numsVoc[target - nums[i]]!)

                break
            }
        }
        return resultA
    }
}

xxxxxxxxxx
 
class Solution {    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {​        var resultA = [Int]()        var numsVoc = [Int: Int]()​        for i in 0...nums.count - 1 {​            // Основное отличие. создаем словарь вида [Int: Int] = [Число: Его позиция в массиве]            numsVoc[nums[i]] = i        }    ​        for i in 0...nums.count - 2 {            // Поиск в словаре разницы            if (numsVoc[target - nums[i]] != nil && numsVoc[target - nums[i]] != i) {​                resultA.append(i)                resultA.append(numsVoc[target - nums[i]]!)​                break            }        }        return resultA    }}

Лучшая оценка этого результата на Leetcode:

Время выполнения: 40 мс
Скорость выполнения — лучше 99.28% всех решений
Потребление памяти — лучше 90.65% решений.

Время — топ, потребление памяти вообще не изменилось.

Что интересного из этого решения я узнал:

Само решение — идти можно от обратного, ища не суммы, а разницу.
Можно немного поработать со словарем для опыта.
Побился с определением того, есть элемент в словаре или нет. Не всегда это очевидно.
Можно поиграться с переборами и улучшением читаемости, но на скорости и потреблении памяти это вряд ли скажется.