Задача с codeward (Sum of pairs)

Question

Вот задачка: https://www.codewars.com/kata/54d81488b981293527000c8f/discuss Решил так:

function sumPairs(ints, s) {
  temp = [];
  for (i in ints) {
    if (temp.includes(s - ints[i])) {
      return [s - ints[i], ints[i]];
    } else {
      temp.push(ints[i]);
    }
  }
}

Проблема в скорости выполнения. При финальной проверке в ints подается строка длиной в 5 000 000 символов. Просто перебрать ее удается, также смог получить все числа, кроме единиц, там ровно по середине массива есть подходящие символы. Можно начать перебирать массив из середины, но это не решение, тут должно быть более интересное и лаконичное решение.

Answer 1

Для ускорения работы можно использовать структуру данных Set. Эта структура хранит в себе только не повторяющиеся элементы. Так например в массиве миллион десяток будет миллион десяток :), а вот в Set всего одна десятка.

Так же преимущество Set перед обычным массивом в том, что сложность функций has и add это O(1), когда у массива поиск элемента занимает O(n). Получается используя структуру Set наш алгоритм имеет сложность O(n), когда с массивом он имел O(n^2)

Вот пример кода:

function sumPairs(ints, s) {
  //Если чисел < 2 то пару мы точно не сможем найти
  if(ints.length < 2)
    return undefined;
  //Объявляем структуру данных Set
  let temp = new Set();
  //Сразу закинем первый элемент, т.к. для него пока что пары точно нет
  temp.add(ints[0]);
  //Проходимся по всему массиву начиная со 2 элемента
  for (let i = 1; i < ints.length; ++i) {
    //Функция has возвращает true если элемент `s - ints[i]` находится
    //в temp, иначе false
    if(temp.has(s - ints[i])){
      return [s - ints[i], ints[i]];
    }
    temp.add(ints[i]);
  }
  //Если по итогу мы так и не наши
  return undefined;
}

Если интересно, то вот тут так же написано об оптимизации решения этой задачи.

БЛОГ НА HUSL

Задача с codeward (Sum of pairs)

Ответы (1 шт):