1d配列Leetcodeソリューションの実行中の合計


難易度 簡単に
よく聞かれる Adobe Amazon (アマゾン) Apple ブルームバーグ ユーバー
配列

問題文

1dの合計を実行中 配列 問題は、結果配列の各インデックスiに対してarr [i] = sum(nums [0]…nums [i])である配列を返さなければならない配列numsが与えられたということです。

 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ループ内の各要素について、別のforループを使用して、元の配列のインデックス0からインデックスiに要素を追加できます。 このアルゴリズムの時間計算量はO(n ^ 2)になります。

単一のものだけを使用することで、この問題の時間計算量を減らすことができます ループ.
numsを指定された配列、resを実行中の合計を格納する配列とすると、res [i]は次のように計算できます。

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

例:nums = [1,2,3,4]を次の図に示します、

1d配列Leetcodeソリューションの実行中の合計

したがって、インデックスiまでの合計がres配列の前のインデックスに格納されているため、プレフィックスの合計を再度計算するためにforループを実行する必要はありません。

製品の導入

1d配列Leetcodeソリューションの合計を実行するためのC ++プログラム

#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]

1d配列Leetcodeソリューションの合計を実行するためのJavaプログラム

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ソリューションの合計を実行するための複雑さの分析

時間の複雑さ

オン) : ここで、nは指定された配列のサイズです。 単一のforループのみを実行しているため、時間計算量は線形になります。

スペースの複雑さ 

オン) : ここでは、サイズnの結果配列を作成しています。 したがって、空間の複雑さも線形になります。