Текущая сумма решения Leetcode 1d массива


Сложный уровень Легко
Часто спрашивают в саман Амазонка Apple Bloomberg Uber
массив

Постановка задачи

В общей сумме 1 пенса массив проблема нам дали массив nums, для которого мы должны вернуть массив, где для каждого индекса i в массиве результатов arr [i] = sum (nums [0]… nums [i]).

Пример

 nums = [1,2,3,4]
[1,3,6,10]

Объяснение:

Текущая сумма: [1, 1 + 2, 1 + 2 + 3, 1 + 2 + 3 + 4] = [1, 3, 6, 10]

nums = [1,1,1,1,1]
[1,2,3,4,5]

Объяснение:

Текущая сумма: [1, 1 + 1, 1 + 1 + 1, 1 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1] = [1, 2, 3, 4, 5]

Подход

В этой задаче мы должны создать массив, в котором значение элемента с индексом i будет равно сумме элементов с 1-го по i-й индексированный элемент в данном массиве.
Для этого мы можем просто создать массив размером, равным заданному размеру массива. Затем для каждого элемента в цикле for мы можем добавить элемент из индекса 0 в индекс i в исходном массиве, используя другой цикл for. Сложность по времени для этого алгоритма будет O (n ^ 2).

Мы можем уменьшить временную сложность этой проблемы, используя только один петля.
пусть nums будет заданным массивом, а res - массивом, в котором мы храним текущую сумму, тогда мы можем вычислить res [i] следующим образом:

res [i] = res [i-1] + nums [i].

пример: nums = [1,2,3,4] показано на рисунке ниже,

Текущая сумма решения Leetcode 1d массива

Следовательно, нам не нужно запускать цикл for для повторного вычисления суммы префикса, потому что у нас уже есть сумма до индекса i, сохраненная в предыдущем индексе массива res.

Реализация

Программа на C ++ для вычисления суммы 1d-массива решения Leetcode

#include <bits/stdc++.h>
using namespace std;

vector<int> runningSum(vector<int>& nums) 
{
    vector<int> res(nums.size());
    if(nums.size()==0) return res;

    res[0]=nums[0];
    for(int i=1;i<nums.size();i++)
    {
        res[i]=res[i-1]+ nums[i];
    }

    return res;

}

int main() 
{
  vector<int> nums={1,2,3,4};
  vector<int> res= runningSum(nums);
  
  cout<<"[";
  
  for(int i=0;i<res.size()-1;i++) cout<<res[i]<<",";
  
  cout<<res.back()<<"]"<<endl;

  return 0; 
}
[1,3,6,10]

Программа на Java для вычисления суммы решения 1d Array Leetcode

import java.lang.*;

class Rextester
{  
    public static int[] runningSum(int[] nums) 
    {
        int[] res= new int[nums.length];
        if(nums.length==0) return res;

        res[0]=nums[0];
        for(int i=1;i<nums.length;i++)
        {
            res[i]=res[i-1]+ nums[i];
        }

        return res;
    }
    
    public static void main(String args[])
    {
        int nums[]={1,2,3,4};
        int res[]= runningSum(nums);

        System.out.print("[");

        for(int i=0;i<res.length-1;i++) System.out.print(res[i]+",");

        System.out.println( res[res.length-1] + "]");
        
    }
}
[1,3,6,10]

Анализ сложности для текущей суммы решения Leetcode 1d массива

Сложность времени

На) : где n - размер данного массива. Поскольку мы выполняем только один цикл for, временная сложность будет линейной.

Космическая сложность 

На) : Здесь мы создаем результирующий массив размером n. Следовательно, сложность пространства также будет линейной.