1d അറേ ലീറ്റ്കോഡ് പരിഹാരത്തിന്റെ ആകെത്തുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു അഡോബി ആമസോൺ ആപ്പിൾ ബ്ലൂംബർഗ് യൂബർ
അറേ

പ്രശ്നം പ്രസ്താവന

1d പ്രവർത്തന തുകയിൽ ശ്രേണി പ്രശ്നം ഞങ്ങൾക്ക് ഒരു അറേ സംഖ്യകൾ നൽകിയിട്ടുണ്ട്, അതിനായി നമുക്ക് ഒരു അറേ തിരികെ നൽകണം, അവിടെ ഓരോ സൂചികയ്ക്കും i ഫല അറേയിലെ arr [i] = sum (സംഖ്യകൾ [0]… അക്കങ്ങൾ [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 മുതൽ ith സൂചികയിലുള്ള മൂലകം വരെയുള്ള മൂലകങ്ങളുടെ ആകെത്തുകയ്ക്ക് തുല്യമായിരിക്കും.
ഇതിനായി നമുക്ക് നൽകിയ അറേ വലുപ്പത്തിന് തുല്യമായ ഒരു ശ്രേണി സൃഷ്ടിക്കാൻ കഴിയും. ഒരു ഫോർ ലൂപ്പിലെ ഓരോ ഘടകത്തിനും നമുക്ക് ഒറിജിനൽ അറേയിലെ ഇൻഡെക്സ് 0 മുതൽ ഇൻഡെക്സ് i ലേക്ക് എലമെന്റ് ചേർക്കാൻ കഴിയും. ഈ അൽ‌ഗോരിത്തിന്റെ സമയ സങ്കീർ‌ണ്ണത O (n ^ 2) ആയിരിക്കും.

സിംഗിൾ മാത്രം ഉപയോഗിക്കുന്നതിലൂടെ ഞങ്ങൾക്ക് ഈ പ്രശ്നത്തിനുള്ള സമയ സങ്കീർണ്ണത കുറയ്‌ക്കാൻ കഴിയും ലൂപ്പ്.
സംഖ്യകൾ‌ തന്നിരിക്കുന്ന അറേ ആയിരിക്കട്ടെ, റൺ‌സ് ഞങ്ങൾ‌ പ്രവർ‌ത്തിക്കുന്ന തുക സംഭരിക്കുന്ന ഒരു അറേ ആയിരിക്കട്ടെ, തുടർന്ന് നമുക്ക് റെസ് [i] ഇനിപ്പറയുന്ന രീതിയിൽ കണക്കാക്കാം:

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

ഉദാഹരണം: അക്കങ്ങൾ = [1,2,3,4] ചുവടെയുള്ള ചിത്രത്തിൽ കാണിച്ചിരിക്കുന്നു,

1d അറേ ലീറ്റ്കോഡ് പരിഹാരത്തിന്റെ ആകെത്തുക

അതിനാൽ, പ്രിഫിക്‌സ് തുക വീണ്ടും കണക്കാക്കാൻ ഞങ്ങൾ ഒരു ഫോർ ലൂപ്പ് പ്രവർത്തിപ്പിക്കേണ്ടതില്ല, കാരണം റെസ് അറേയുടെ മുമ്പത്തെ സൂചികയിൽ ഞാൻ സംഭരിച്ച സൂചിക വരെ ഞങ്ങൾക്ക് ഇതിനകം തന്നെ തുകയുണ്ട്.

നടപ്പിലാക്കൽ

1 ഡി അറേ ലീറ്റ്കോഡ് സൊല്യൂഷന്റെ തുക പ്രവർത്തിപ്പിക്കുന്നതിനുള്ള സി ++ പ്രോഗ്രാം

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

1 ഡി അറേ ലീറ്റ്കോഡ് സൊല്യൂഷന്റെ തുക പ്രവർത്തിപ്പിക്കുന്നതിനുള്ള ജാവ പ്രോഗ്രാം

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]

1 ഡി അറേ ലീറ്റ്കോഡ് പരിഹാരത്തിന്റെ ആകെത്തുക പ്രവർത്തിപ്പിക്കുന്നതിനുള്ള സങ്കീർണ്ണ വിശകലനം

സമയ സങ്കീർണ്ണത

O (n): ഇവിടെ n എന്നത് തന്നിരിക്കുന്ന അറേയുടെ വലുപ്പമാണ്. ഞങ്ങൾ ലൂപ്പിനായി ഒരൊറ്റ ഭാഗം മാത്രം പ്രവർത്തിപ്പിക്കുന്നതിനാൽ സമയ സങ്കീർണ്ണത രേഖീയമായിരിക്കും.

ബഹിരാകാശ സങ്കീർണ്ണത 

O (n): ഇവിടെ നമ്മൾ n ന്റെ വലുപ്പത്തിന്റെ ഒരു ഫല ശ്രേണി സൃഷ്ടിക്കുന്നു. അതിനാൽ സ്ഥല സങ്കീർണ്ണതയും രേഖീയമായിരിക്കും.