दिइएको एर्रेको लागि सबै अद्वितीय सब-एरे योगको योगफल पाउनुहोस्


कठिनाई तह सजिलो
बारम्बार सोधिन्छ अमेजन फेसबुक ग्रेऑरेंज Intuit माइक्रोसफ्ट नागररो
एरे हैश क्रमबद्ध

मानौं तपाईंसँग पूर्णाgers्कहरूको एरे छ। समस्या "दिइएको एर्रेको लागि सबै अद्वितीय सब-एरे योगको योग फेला पार्नुहोस्" सबै अद्वितीय उप-एर्रेहरूको योग पत्ता लगाउन सोध्छ (सब एरे योग प्रत्येक उप-एर्रेको तत्वहरूको योग हुन्छ)।

अद्वितीय उप-एर्रे योगबाट, हामीले भन्न खोज्यौं कि कुनै उप-एरेको समान मूल्य छैन।

उदाहरणका

arr[] = {3, 1, 4, 5}
44
arr[] = {2,1,3,6}
36

दिइएको एर्रेको लागि सबै अद्वितीय सब-एरे योगको योगफल पाउनुहोस्

अल्गोरिदम

  1. घोषणा गर्नुहोस् नक्सा.
  2. सेट उत्पादन लाई 0.
  3. I = 0, बाट i सम्म एरे ट्रान्सवर्स गर्नुहोस्
    1. सेट गर्नुहोस् sum 0 मा।
    2. J = i, j बाट एरे ट्राभर्स गर्नुहोस्
      • योगमा जोडमा एर [j] को मान थप्नुहोस्।
      • योग र यसको घटनालाई नक्सामा थप्नुहोस्।
  4. नक्सालाई ट्रान्सभ गर्नुहोस् र ती कुञ्जीहरूका प्रविष्टिहरू जाँच गर्नुहोस् जसको मान १ छ।
    1. आउटपुटमा कुञ्जीहरूको मान थप गर्नुहोस् जब हामी सर्त सन्तुष्ट पाउँछौं।
  5. फिर्ता आउटपुट

स्पष्टीकरण

हामीलाई दिइएको छ पूर्णांक array। हाम्रो कार्य भनेको सबै अद्वितीय उप-एर्रेहरूको योग पत्ता लगाउनु हो। प्रत्येक उप-एर्रेको योगफल प्रत्येक उप-एर्रेको तत्वको योग हुनेछ। हामी प्रयोग गर्न जाँदैछौं हसिhing यो प्रश्न समाधान गर्न। हामी एउटा एर्रेको प्रत्येक एलिमेन्ट लिन्छौं, ० लाई जोडेर आरम्भ गर्दै, जब हामी i को मान परिवर्तन गर्दछौं। जब हामी भित्री लुपमा प्रवेश गर्छौं, हामी एउटा एरे बाट पार गर्छौं i लाई n, र एरे र योगको प्रत्येक मान थप्न। त्यसो भए हामी सँगै जोड र यसको नक्साहरू नक्शामा भण्डार गर्दछौं। सम्पूर्ण एर्रे भ्रमण गरे पछि सब एर्रेको सम्भावित योग फेला पार्नुहोस्। त्यस पछि, हामी नक्सामा ती योगफलहरू खोज्छौं जसको घटना केवल एक पटक हुन्छ। किनभने हामी अद्वितीय उप-एर्रेको योग चाहान्छौं, जसको अर्थ भिन्न योगफल हो। त्यसोभए जब हामी नक्शामा जोड फेला पार्छ जुन एक पटक हुन्छ, जसको आवृत्ति १ हो भन्न खोज्नुपर्दछ, हामी जोडेर इनपुटमा ती योगफलहरूको मूल्य अपडेट गर्नेछौं।

यसको लागि उदाहरण विचार गर्दै:

उदाहरणका

एर [] = {,, १,,,}}

पहिले, हामीसँग i = ० छ, तब हामीसँग एलिमेन्टको रूपमा have छ र हामी from बाट सुरु गर्नेछौं, हामी जोडमा adding थप्दैछौं र 0 लाई नक्शामा अपडेट गर्नेछौं, तब जोडमा १ थप्नेछौं, र the लाई नक्शामा अपडेट गर्दैछौं। , त्यसपछि योगमा element तत्वको रूपमा लिदै नक्शामा adding थप्दै। यस तरिकाले, हामी पहिलो ट्राभर्सल समाप्त हुनेछ 3 भ्रमण र नक्शामा १२ अपडेट गरेपछि।

त्यसोभए जब हामी an एलिमेन्टको रूपमा लिन्छौं र from बाट सुरु गर्दछौं, हामी जोडलाई नक्शामा अपडेट गर्नेछौं, किनकि 4 पहिले नै यसमा छ नक्सा, हामी केवल यसको फ्रिक्वेन्सी बढाउनेछौं, र हामी ती योगफलहरूको बेवास्ता गर्दछौं जसको फ्रिक्वेन्सी १ छैन। यस तरीकाले हामी अद्वितीय उप-एर्रेहरू ह्यान्डल गर्न सक्षम हुनेछौं।

कोड

C ++ कोड दिईएको एर्रेको लागि सबै अद्वितीय सब-एरे योगको योग पाउन

#include<iostream>
#include<unordered_map>

using namespace std;

int findSumOfUnique(int arr[], int n)
{
    int output = 0;
    unordered_map<int, int> MAP;

    for (int i = 0; i < n; i++)
    {
        int sum = 0;
        for (int j = i; j < n; j++)
        {
            sum += arr[j];
            MAP[sum]++;
        }
    }
    for (auto entry : MAP)
        if (entry.second == 1)
            output += entry.first;

    return output;
}
int main()
{
    int arr[] = { 3, 1, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << findSumOfUnique(arr, n);
    return 0;
}
44

जाभा कोड दिइएको एरेका लागि सबै अद्वितीय सब-एरे योगको योग पाउन

import java.util.HashMap;
import java.util.Map;

class SumUniqueSubArray
{
    public static int findSumOfUnique(int []arr, int n)
    {
        int output = 0;

        HashMap<Integer,Integer> MAP = new HashMap<Integer,Integer>();
        for (int i = 0; i < n; i++)
        {
            int sum = 0;
            for (int j = i; j < n; j++)
            {
                sum += arr[j];
                if (MAP.containsKey(sum))
                {
                    MAP.put(sum, MAP.get(sum) + 1);
                }
                else
                {
                    MAP.put(sum, 1);
                }
            }
        }
        for (Map.Entry<Integer,Integer> entry : MAP.entrySet())
            if (entry.getValue() == 1)
                output += entry.getKey();

        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = {3, 1, 4, 5};
        int n = arr.length;
        System.out.println(findSumOfUnique(arr, n));
    }
}
44

जटिलता विश्लेषण

समय जटिलता

O (n2जहाँ "N" एर्रेमा एलिमेन्ट्सको संख्या हो। किनकि हामीले २ नेस्टेड लूपहरू प्रयोग गरेका छौं र हेशम्याप प्रयोग गरेर ओ (१) मा योगफल खोजिएको छ।

ठाउँ जटिलता

O (n ^ 2) जहाँ "N" एर्रेको एलिमेन्ट्सको संख्या हो। किनभने सबैभन्दा नराम्रो अवस्थामा हामीसँग n ^ 2 बिभिन्न उप-एरे योग हुन सक्छ।