Задача на поиск чисел для заданной суммы Sum Two

Нужно реализовать функцию, в которую передают 2 аргумента: массив чисел nums и число target. Функция должна вернуть индексы двух чисел из массива, сумма которых равна target

↓ Смотреть видео ↓

Пример

Input: nums = [2,7,3,5], target = 5
Output: [0,1]
Explanation: Потому что nums[0] + nums[2] == 5, возвращаем [0, 2].

Наивное решение проблемы

Самый простой и очевидный способ будет сделать два вложенных цикла for, пробежаться по массиву nums перебирая каждую пару индексов.

const findSum = function(nums, target) {
  for(let i = 0; i < nums.length; i++){
    for(let j=0; j < nums.length; i++){
      if(i===j) continue;
      const sum = nums[i] + nums[j];
      if(sum === target) return [i, j];
    }
  }
}

Данный способ возможно простой для понимания. И это один из первых решений которые обычно приходят в голову. Тем не менее в нем есть огромный недостаток. Давайте узнаем big O данного решение. Нас интересует скорость, или кол-вот операций. Так как мы используем вложенный цикл for это будет кубическая формула, т.е. O(n^2). Что это значит? Да то что если в массиве 100 чисел, то данному алгоритму понадобиться до 10 000 повторений чтобы найти сумму.

Как ускорить алгоритм?

Итак, чтобы решать не наивным способом сначало стоит начать с вопросов. К примеру, что такое сумма? Это a + b = c. Где в нашем условии c? - это target, верно? А как нам найти b если известно a? b = c - a Т.е. если мы напишем только один цикл, то на каждой итерации (на каждом повторе цикла) наше nums[i] и будет a. Значит сможем найти b. Но как за единицу времени O(1) узнать индекс элемента в массиве? Для этого нам понадобиться перевести массив в обьект, где каждое значение массива будет ключом, а индекс - "парой" значением.

Решаем задачу за линейное время

Если быть совсем точным то время будет O(2*n) но так как константы игнорируются - остается O(n)

const findSum = function(nums, target) {
  // переводим массив в объект
  let numsObj = {}
  for(let i = 0; i < nums.length; i++){
      numsObj[nums[i]] = i;
      const diff = target - nums[i];
      if((numsObj[diff]  || numsObj[diff] === 0) && i !== numsObj[diff]){
          return [numsObj[diff], i]
      }
  }
  //  узнаем и затем находим индекс разницы в созданном объекте
  for(let i = 0; i < nums.length; i++){
    const diff = target - nums[i];
      if((numsObj[diff]  || numsObj[diff] === 0) && i !== numsObj[diff]){
        return [numsObj[diff], i]
      }
    }
  };

Watch Now