Выконваецца сума 1d масіва Leetcode Solution


Узровень складанасці Лёгка
Часта пытаюцца ў Саман амазонка яблык Bloomberg Uber
масіў

Пастаноўка праблемы

У бягучай суме 1г масіў праблема, мы атрымалі нумар масіва, для якога мы павінны вярнуць масіў, дзе для кожнага індэкса i ў выніковым масіве arr [i] = сума (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] + нумары [i].

прыклад: nums = [1,2,3,4] паказана на малюнку ніжэй,

Выконваецца сума 1d масіва Leetcode Solution

Такім чынам, нам не трэба запускаць цыкл for, каб зноў вылічыць суму прэфікса, таму што ў нас ужо ёсць сума да індэкса i, які захоўваецца ў папярэднім індэксе масіва res.

Рэалізацыя

Праграма C ++ для бягучай сумы 1d-масіва Leetcode Solution

#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-масіва Leetcode Solution

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]

Аналіз складанасці для бягучай сумы 1d-масіва Leetcode Solution

Складанасць часу

O (n): дзе n - памер дадзенага масіва. Паколькі мы запускаем толькі адзін цыкл for, такім чынам, складанасць часу будзе лінейнай.

Касмічная складанасць 

O (n): Тут мы ствараем выніковы масіў памерам n. Такім чынам, складанасць прасторы таксама будзе лінейнай.