В сегодняшней публикации мы собираемся решить культовую задачу программирования: Two Sum. Для большинства людей эта проблема довольно тривиальна, но для других это отличное место для начала и действительно демонстрирует сильные стороны определенных структур данных, и в этой статье мы рассмотрим пошаговое решение и анализ. .
Две суммы
'Учитывая массив целых чисел nums
и целое число target
, возвращают индексы двух чисел таким образом, что они в сумме составляют target
' - вы можете получить варианты этой проблемы, но в целом она включает список целых чисел и вам будет дано «целевое» значение, которого нужно достичь. Целевое значение формируется путем сложения 2 целых чисел из списка.
Мы наложим некоторые ограничения, чтобы сделать эту проблему более простой:
- Будет существовать только один действительный ответ, например задано: [1, 3, 5, 2, 12], 7. Только 5 + 2 приведет к 7. Массив, подобный [4, 3, 5, 2, 12], НЕ будет вводиться как 4 + 3 или 5 + 2 являются допустимыми выходами.
- Целое число можно использовать только один раз, например задано [1, 2, 3, 5], 6. Единственный допустимый выход - 5 + 1, 3 не может использоваться дважды как 3 + 3.
// Some test cases to try out on your own const twoSum = (array, target) => { // insert your solution here } const arr1 = [3, 4, 5, 6, 7]; const target1 = 8; // should return, [0,2] > 3 + 5 = 8 const arr2 = [34, 23, 35, 24, 2, 7, 11] const target 2 = 47; // should return, [1, 3] const arr3 = [7,7] const target3 = 14 // should return [0,1]
Попробуйте и посмотрите ниже грубую силу, однопроходный и двухпроходный подход.
Наивный подход:
Методом грубой силы для этого было бы создание вложенного цикла. Довольно просто, перебрать каждый элемент (n) в данном массиве и создать другой цикл, который ищет значение, равное target — n
. Это будет выглядеть примерно так:
const twoSum = (array, target) => { for ( let i = 0; i < array.length; i++) { for ( let j= i++; i< array.length; j++) { if ( array[j] === target - array[i]) return [i, j] }; }; return null; };
Если мы что-то знаем о вложенных циклах, так это то, что у них ужасное время выполнения. O (n²), если входной массив вырастет до миллиона элементов, время выполнения, следовательно, будет расти экспоненциально. Существует лучшее решение, которое можно запустить за O (n) раз.
Двухходовой и однопроходный подходы
Следующие решения используют хэш-таблицу, см. Мою статью здесь для обзора хэш-таблиц и их использования. Хеш-таблица - это очень полезная структура данных для использования в этой проблеме, поскольку вставка, удаление и поиск выполняются за время O (1), пока мы знаем ключ, который ищем.
В двухпроходном решении мы будем заполнять таблицу парами элемент: индекс. Второй цикл будет проверять нашу хеш-таблицу, существует ли complement = target — hashtable[i]
, и возвращать индексы, иначе мы вернем num.
const twoSum = (array, target) => { const hashtable = {}; for ( let i = 0; i < array.length; i++) { hashtable[nums[i]] = i; }; for ( let j= 0; j< array.length; j++) { let complement = target - array[j] // The second condition checks for cases like twoSum([7,7], 14) where the indices of similar elements MUST be different if ( hashtable.hasOwnProperty(complement) && hashtable[complement] !== j) { return [hashtable[complement], j] } }; return null; };
Использование хеш-таблицы снижает временную сложность до O (2n), что является огромным улучшением по сравнению с O (n²), с которой мы изначально начали. Сложность пространства увеличилась до O (n), потому что теперь мы используем хеш-таблицу для хранения индексов каждого элемента.
Вышеупомянутое решение также может быть дополнительно оптимизировано до однопроходного алгоритма, поскольку мы можем проверять дополнение и добавлять элементы и индексы в хеш-таблицу за один проход.
const twoSum = (array, target) => { const hastable = {}; for ( let i = 0; i < array.length; i++) { let complement = target - array[i]; if ( hashtable.hasOwnProperty(complement)){ return [hashtable[complement], i] } hashtable[array[i]] = i; }; return null; };
Вышеупомянутое решение является однопроходным и дополнительно оптимизирует временную сложность нашего решения до O (n). На мой взгляд, двухпроходное решение было немного более интуитивным, и то, к чему я пришел сначала, но мы улучшаем наши навыки с DS и Algo, мы можем оптимизировать наши решения, чтобы получить ответ, аналогичный приведенному выше.
По мере того, как мы подходим к завершению нашей серии статей о структурах данных, я буду освещать некоторые популярные проблемы кодирования, а также писать о новых технологиях, в которые я вникаю.