Рубрики
Без рубрики

Алгоритмы: Сумма диапазона

Это снова алгоритм! Это легкий код, но из этого есть многому. Ей… Tagged with Alogrithms, JavaScript.

  • Автор записи Автор: tang
  • Дата записи 30.05.2022

Это снова алгоритм!

Это легкий код LeetCode , но из этого есть чему научиться.

Вот проблема:

Сумма диапазона :

Учитывая целочисленные массивы, найдите сумму элементов между индексами i и j (i ≤ j), включительно.

Итак, если у нас есть множество, скажем, [1,2,3,4,5] и индексы 2 и 4 , мы бы добавили 3 + 4 + 5 получить 12 Анкет

Довольно просто, верно? Мы можем просто зацикливаться на нашем массиве и подвести итог между тем (и включая) индексы, которые мы получаем.

function NumArr(arr){
  this.data = arr;
}

NumArr.prototype.rangeSum = function(i, j){
  let output = 0;
  for(i; i<=j;i++){
    output+=this.data[i];
  }
  return output;
}

Это не ужасное решение. Если мы запросим наш массив только один или два раза, или если мы ожидаем получить различные массивы, это работает. Компьютеры очень хороши в дополнении- Возможно, самая быстрая операция, которую ЦП может сделать Анкет На самом деле, это настолько быстро, что на самом деле проходит тесты LeetCode.

Тем не менее, есть два условия, которые дают нам место для улучшения и оптимизации нашего решения.

  1. Вы можете предположить, что массив не меняется.
  2. Есть много вызовов для функции Sumrange.

Итак, давайте подумаем о том, как это работает. Если мы делаем достаточное количество сумм, некоторые из них, вероятно, достигнут того же диапазона, верно? Мы можем кэшировать наше решение и искать его вместо того, чтобы переоценить его. Давайте положим кеш на конструкторе.

Кэширование

Какую форму должен принять кэш? Если мы думаем об этом на минуту, двухмерный массив, кажется, имеет больше всего смысла- мы добавляем диапазон от я к J , чтобы мы можем сбросить наши кэшированные результаты в this.cache [i] [j]

function NumArray(arr){
  this.data = arr;
  this.cache = arr.map(()=>[]); //fill cache with one empty array per item in arr
}

NumArray.prototype.sumRange = function(i, j){
  if(!this.cache[i][j]){
    let output = 0;
    for(let k = i; k<=j;k++){
      output+=this.data[k];
    }
    this.cache[i][j] = output;
  }
  return this.cache[i][j];
}

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

Есть еще лучшее решение?

Короткий ответ: да. очень да.

Добраться туда была немного боли. Первоначально я посмотрел на решение LeetCode и увидел кое -что о предварительном обязанности результатов. Я воспринял это, чтобы означать, что мы должны предварительно рассчитывать и кэшировать все это- и почему бы и нет?

Если мы вычисляем какую -либо сумму диапазона, мы выполняем повторную работу. то есть, если мы суммируем значения из индекса 0 Индекс 5 , мы рассчитали arr [0]+arr [1] , arr [0]+arr [1]+arr [2] , и т. д. и т. д. Это означает, что мы можем просто кэшировать некоторые из этих промежуточных значений по мере продвижения.

Я мог бы интуитивно, чтобы, по крайней мере, получить первый набор сумм, подобных этим:

function NumArray(arr){
  this.data = arr;
  this.cache = []
  arr.reduce((acc,val)=>{
    acc += val;
    cache.push(val)
    return acc;
  },0)
}

Когда это заканчивает вычисления, наш кэш будет массивом со всеми суммами от 0 к n Анкет [(сумма индекса 0), (сумма индекса 0 до индекса 1), (сумма индекса 0 до индекса 2), ...., (сумма индекса 0 к индексу n)]]]

Это приятные вычисления, которые облегчают нашу жизнь, но как бы мы подумали о том, чтобы получить все суммы Индекс 1 для индекса n , тогда Индекс 2 для индекса n , вплоть до Индекс N-1 для индекса n ?

Я попытался выяснить, был ли простой способ вычислить все возможные суммы, но продолжал получать O (n^2) Решения, которые пройдут на LeetCode.

Поэтому я попытался выяснить, какие шаблоны я мог видеть в тестовом случае, моделируя его вручную с очень простым массивом [0,1,2,3,4]

Есть несколько интересных вещей. Мы видим, что каждая последовательная строка в основном производится, взяв предыдущий ряд и вычитая любое целое число, которое мы пропускаем.

Первый ряд сделан путем суммирования всех чисел. Второй ряд можно сделать, взяв первую строку и вычитая первое число. Третий ряд можно сделать, взяв второй ряд и вычитая второй номер, четвертый ряд можно сделать, взяв третий ряд и вычитая третий номер.и так далее.

Это потребовалось немного, чтобы погрузиться, но секрет здесь зависит от перестройки этого предыдущего понимания:

Другими словами, мы можем найти любой диапазон от я к J взяв сумму чисел из индекса 0 к J и вычитание суммы чисел из индекса 0 к i .

В связи с этим, все необходимые нам данные создаются, когда мы делаем наш первоначальный проход. У нас гарантированно есть соответствующая сумма для индекса 0 к я , а также для индекса 0 к j . Нам даже не нужно кэшировать каждый возможный ответ, чтобы иметь O (1) операция

Вот как выглядит мой последний результат:

const NumArray = function(nums){
  this.cache = [0]; // done to avoid an "if" check for the first number
  for (let i = 0; i < nums.length; i++){
    this.cache.push(this.cache[i]+nums[i]);
  }
}

NumArray.prototype.sumRange = function(i,j){
  return this.cache[j+1]-this.cache[i];
}

Это очень экономит на сложности времени- Наш первоначальный проход через массив На) , что является той же сложностью времени, что и расчет единой суммы диапазона в первую очередь (то есть, если вы хотите суммировать от 0 к arr.length-1 ) После этого получить какие -либо последовательные ответы – это O (1) Операция!

Единственный реальный компромисс заключается в том, что пространственная сложность этого решения также является На) , Но это того стоит.

Оригинал: “https://dev.to/tttaaannnggg/algorithms-range-sum-query-2hcf”

Читайте ещё по теме: