Эту задачу должен уметь решать каждый! Классическая задача на интервью

[@АлександрРуденко-п5к]

Спасибо за задачу! Для меня как начинающего это огромная щедрость!

[@Yarikorg]

Не считаю себя программистом, но тоже сразу думал про поиск пары. Но я пайтон не знаю, можно сказать, думал, что есть уже отдельный метод поиска индекса в массиве по значению элемента, тогда и базу создавать не пришлось бы. Понятно, что на примитивном уровне это было бы тоже самое. Задача не сложная, приятно осознавать, что что-то можешь.))

[@ДмитрийДеньщиков-т1т]

более идеальное решение в ответах на литкоде - самый быстрый по времени ответ на эту задачу. контент там для эпилога к видео самое то! кто не смотрел рекомендую глянуть...

[@АлександрРуденко-п5к]

У меня возник вопрос как у начинающего. В цикле был перебор i и num, получается что i будет принимать 2 числа - это сам элемент после перебора enumerate и его индекс? А как тогда индекс элемента из словаря db будет равен i, если i - это 2 числа? А в целом всё остальное понятно и интересно!

[@GlebMikhaylov]

Нет, i будет только индексом -- так работает enumerate

[@luckyday556]

Думаю метод указателей тоже отлично подойдёт

[@GlebMikhaylov]

Только для отсортированного массива! На LeetCode для него даже отдельную задачу сделали leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/

[@goodnight_88]

а как понять какие операции какую сложность/память имеют? Вот типа фраза "пробивка по базе это константа", а почему так?

[@vadimselin4386]

Это из-за устройства хэш-сетов и хэш-таблиц. Доступ к любому элементу там осуществляется по значению хэш-функции для этого элемента. Направление и «лопату» я дал, дальше дело за вами, мой друг🤜🤛

[@GlebMikhaylov]

Вот тут есть все "расценки" www.bigocheatsheet.com/

[@grushel]

а почему у нас пространственная сложность O(1), а не О(n)? Ведь нам нужно будет всегда n места в памяти (сам входной массив), чтобы решить эту задачу

[@rememberme8869]

Потому что дополнительная память не выделяется и идёт работа только с входным массивом. Не создаются новые массивы, например. Переменные тоже считаются за выделение памяти, но обычно они выделяются фиксировано. Допустим я присвою x = 3 y = 4 z = 9 Получается затрат памяти О(3), но О большая "съедает" константу, а значит получается О(1) Дополнено: допустим О(2*n*log(n) + n) тоже будет O(2nlog(n)), потому что n*log(n) растёт быстрее и потом съедаем константу и получаем О(n*log(n))

[@GlebMikhaylov]

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

[@djo8995]

Перебор совсем тупой: зачем для j перебирать весь массив? Взял i и j перебираешь от i+1 до конца списка и т.д. и условие i==j уже не нужно. переборов меньше, время меньше

[@GlebMikhaylov]

Да, тут можно так оптимизировать, но на сложность по времени это не повлияет, она все равно останется O(n**2). Я решил не писать эту оптимизацию, чтобы не отвлекать от решения со словарем

[@СенчуринНиколай]

ну оптимальнее, да, но n^2 все равно никуда не делся, а, ну выше Глеб и отписал