У вас есть два целочисленных массива
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; }
Когда я проверил другие решения, они были довольно похожи, так что я не слишком огорчился, ха!