У вас есть два целочисленных массива a и b и целое целое значение v. Определите, существует ли пара чисел, в которой одно число взято из a, а другое - из b, которые можно сложить вместе, чтобы получить сумму v. Верните true, если такая пара существует, в противном случае верните false. - по CodeFights

Этот начинался как sumOfTwo.rb, но я не мог пройти «скрытые тесты», потому что они выполнялись слишком долго, поэтому я отказался от этого.

Я вернулся сегодня утром, чтобы написать его на JavaScript. Я хотел написать и запустить свой код локально, поэтому я установил Node.js и приступил к работе.

Мне не удалось заставить мое оптимизированное решение Ruby пройти все тесты, поэтому я начал с этого действительно простого решения:

function sumOfTwo(a, b, v) {
   for(var x = 0; x < a.length; x++) {
        for(var y = 0; y < b.length; y++){
            if(a[x] + b[y] == v) { 
             return true; 
            }
        }
    }
    
    return false;
}

Наихудший сценарий для этого решения состоит в том, что последние элементы в каждом массиве являются единственной комбинацией, которая в сумме дает заданное число (v), поэтому O (n²). This - хороший обзор нотации Big O.

Прежде чем я начал оптимизацию, я настроил измерение времени выполнения, потому что мое оптимизированное решение Ruby все еще не удавалось. Итак, я возился с этим все утро. Я добавил код для таймингов и кучу мусорного кода для генерации случайных массивов и записи их в файлы для повторного тестирования, а также код для проверки наихудшего сценария. На заметку: ищите тестовые среды и инструменты Node.js в npm

После того, как я все это установил, я провел быструю оптимизацию, и она сработала! Вместо того, чтобы проверять каждую комбинацию, просмотрите один массив и проверьте число, которое вам нужно сделать v в другом массиве. Намного быстрее выполнить цикл по каждому массиву один раз, max… это меняет это значение на O (n). Это не самый красивый код, но он проходит все тесты CodeFights, так что это круто.

function sumOfTwo(a, b, v) {
    var ah = [];
    for(var x = 0; x < a.length; x++) {
       var i = v - a[x];
       ah[i] = a[x];
    }
    
    for(var y = 0; y < b.length; y++) {
       if(ah[b[y]] != null) {
          return true;
       }
    }
    return false;
}

Когда я проверил другие решения, они были довольно похожи, так что я не слишком огорчился, ха!