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