१d एरे लेटकोड समाधानको योगफल


कठिनाई तह सजिलो
बारम्बार सोधिन्छ एडोब अमेजन एप्पल ब्लूमबर्ग Uber
एरे

समस्या वक्तव्य

१d को दौडमा array समस्या हामीलाई एउटा एर्रे नम्बर दिइएको छ जसको लागि हामीले एउटा एरे फिर्ता गर्नुपर्नेछ जहाँ प्रत्येक अनुक्रमणिका i को लागि परिणाम एर्रेमा [i] = योग (संख्याहरू [०]… संख्याहरू [i])।

उदाहरणका

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

व्याख्या:

चालु योग हो: [१, १ + २, १ + २ +,, १ + २ + + +]] = [१,,,,, १०]

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

व्याख्या:

चालु योग हो: [१, १ + १, १ + १ + १, १ + १ + १ + १, १ + १ + १ + १ + १] = [१, २,,,,,]]

दृष्टिकोण

यस समस्यामा हामीले एउटा एरे सिर्जना गर्नुपर्नेछ जहाँ इन्डेक्सको एलिमेन्ट i को मान १ बराबरको ith अनुक्रमित एलिमेन्टमा दिइएको एरेमा योगको बराबर हुनेछ।
यसको लागि हामी केवल दिइएको एरे साइज बराबर साइजको एर्रे सिर्जना गर्न सक्छौं। त्यसपछि लुपको लागि प्रत्येक एलिमेन्टको लागि हामी एलिमेन्ट ० सूचीबाट अनुक्रमणिका i लाई मूल एर्रेमा लूपको लागि अर्को प्रयोग गरेर थप्न सक्छौं। यस एल्गोरिथ्मको लागि समय जटिलता ओ (n ^ 0) हुनेछ।

हामी केवल एकल प्रयोग गरेर यो समस्याको लागि समय जटिलता कम गर्न सक्छौं लुप.
नम्बरहरू दिइएको एर्रे र रेजमा एक एरे हुन दिनुहोस् जसमा हामी चलिरहेको योग भण्डार गर्दैछौं, त्यसपछि हामी रेस गणना गर्न सक्दछौं [i] निम्न रूपमा:

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

उदाहरण: संख्या = [१,२,1,2,3,4] तल चित्रमा देखाइएको छ,

१d एरे लेटकोड समाधानको योगफल

त्यसैले हामी फेरि उपसर्ग योग गणना गर्न लूप को लागी रन गर्न आवश्यक छैन किनकि हामी पहिले नै पुनःसूची एर्रे को पछिल्लो अनुक्रमणिका मा सूचकांक सम्म भण्डार सम्म योग छ।

कार्यान्वयन

C ++ कार्यक्रम १d एरे लेटकोड समाधानको चालु योगको लागि

#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 एरे लेटकोड समाधानको योगको लागि चालु जाभा कार्यक्रम

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]

१d एरे लेटकोड समाधानको योगफलको लागि जटिलता विश्लेषण

समय जटिलता

O (n): जहाँ n दिइएको एरेको आकार हो। किनकि हामी लूपको लागि मात्र एकल चलाइरहेका छौं, त्यसैले समय जटिलता रैखिक हुनेछ।

ठाउँ जटिलता 

O (n): यहाँ हामी n को आकारको नतिजा एरे सिर्जना गर्दैछौं। त्यसैले अन्तरिक्ष जटिलता पनि रैखिक हुनेछ।