Две суммы | Вызов кодирования — Leetcode
Всем привет.
Я начал этот проект, чтобы поделиться своими знаниями по различным темам, связанным с наукой, программированием (структуры данных, алгоритмы, парадигмы), технологиями, математикой и другими.
В этом сезоне я поделюсь некоторыми способами решения некоторых проблем платформы Leetcode. Эти проблемы относятся к категории «Вопросы для интервью» и применяются к некоторым крупным технологическим компаниям, таким как Google, Facebook, Microsoft, Twitter и так далее. Без дальнейших церемоний, давайте начнем.
Две суммы
1. Использование подхода грубой силы
Однако при реализации этой идеи его временная сложность является квадратичной.
2. Использование хеш-таблицы/словаря
Как только у нас появится представление о грубой силе, мы сможем улучшить ее, используя словарь, в котором будет отображаться каждый из индексов. с соответствующим значением.
Кроме того, мы будем использовать дополнение, чтобы найти значение, которое удовлетворяет соотношению справа, где «x» — это дополнение .
Мы сокращаем время поиска с O(n²) до O(1), изменяя пространство на скорость
Facebook: https://tinyurl.com/y6sey6n2
Instagram: https://www.instagram.com/dile.al.kai/
Youtube: https://youtu. быть/-3_WB8XYT-8