Программирование
Задачи с собеседований: Leetcode — Сумма двух
Задача
Дан массив целых чисел 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 } }
Лучший результат на 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 } }
Лучшая оценка этого результата на Leetcode:
- Время выполнения: 40 мс
- Скорость выполнения — лучше 99.28% всех решений
- Потребление памяти — лучше 90.65% решений.
Время — топ, потребление памяти вообще не изменилось.
Что интересного из этого решения я узнал:
- Само решение — идти можно от обратного, ища не суммы, а разницу.
- Можно немного поработать со словарем для опыта.
- Побился с определением того, есть элемент в словаре или нет. Не всегда это очевидно.
- Можно поиграться с переборами и улучшением читаемости, но на скорости и потреблении памяти это вряд ли скажется.
Что дальше
Решаем вторую задачу из легкий — Номер палиндрома. Уже, наверное, без гугления алгоритмов :).
Есть предложения по улучшению кода? Напишите в наш чат!