В сегодняшней публикации мы собираемся решить культовую задачу программирования: 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, мы можем оптимизировать наши решения, чтобы получить ответ, аналогичный приведенному выше.

По мере того, как мы подходим к завершению нашей серии статей о структурах данных, я буду освещать некоторые популярные проблемы кодирования, а также писать о новых технологиях, в которые я вникаю.