Алгоритм решения задач: задача с двумя и тремя суммами
ОБНОВЛЕНИЕ. В настоящее время статья содержит методы грубой силы для решения задачи с тремя суммами. Скоро будут обновлены лучшие подходы.
Я начал изучать Пришествие кода на 2020 год. В первый день сценарий включал в себя написание программы для поиска произведения n чисел, которые в сумме дают заданное целевое значение суммы. Итак, в идеале найти эти два/три элемента — это ключ. В этой статье объясняются различные способы достижения этого.
Постановка задачи для задачи на две суммы
Учитывая массив целых чисел nums и целое число target_sum, верните два числа так, чтобы в сумме они составлялиtarget_sum.
Например, предположим, что ваш образец ввода содержит следующее, а указанная целевая сумма равна 2020.
1721
979
366
299
675
1456В этом списке две записи, которые в сумме дают 2020, это 1721 и 299.
Подход 1: грубая сила
Метод грубой силы прост. Переберите каждый элемент x и найдите другое значение y, равное y = target_sum — x.
Подход 2: Использование хэш-карт.
Компромисс между временной сложностью и пространственной сложностью — наоборот, в нашем втором подходе мы создадим hashMap. в первом цикле for мы перебираем массив и назначаем push элементам в hashMap.
Во втором цикле for мы используем hasOwnProperty и пытаемся найти элемент дифференциального значения между target_sum и текущим элементом индекса.
Постановка задачи для задачи трех сумм
Дан массив nums из n целых чисел. Существуют ли элементы a, b, c в nums такие, что а + b + c = target_sum? Найдите все уникальные триплеты в массиве, сумма которых равна target_sum.
Например, предположим, что ваш образец ввода содержит следующее, а указанная целевая сумма равна 2020.
1721
979
366
299
675
1456В приведенном выше списке три записи, которые в сумме дают 2020, это 979, 366 и 675.
Подход 1: грубая сила
В этом подходе мы пытаемся вычислить сумму для текущего элемента (полученного с использованием первого цикла for) со следующими двумя последующими элементами (полученными с использованием следующих циклов for).
Внесение некоторых поправок
В приведенном выше подходе индексы для каждой переменной i, j и k посещаются более необходимого количества раз. Таким образом, создаются дубликаты записей. Мы могли бы избежать этого, просто отслеживая посещенные индексы следующим образом. Время, необходимое для выполнения, будет почти таким же, но мы, по крайней мере, избавимся от дубликатов.
Уточнение кода в самом внутреннем цикле
Как и в подходе Two Sum 2, мы можем использовать метод Array.find() в самом внутреннем цикле for, чтобы он выглядел красиво (это не влияет на текущую временную сложность).
Приведенные выше решения не оптимизированы для использования минимального времени выполнения. тем не менее, они, по крайней мере, заставят вас начать пересматривать, как вы думаете, с точки зрения динамического программирования.
Узнайте больше об описаниях проблем adventOfCode и их решениях в моем одноименном репозитории GitHub. Ссылка здесь
