Գտեք տրված զանգվածի համար բոլոր յուրահատուկ ենթադասերի զանգվածի գումարը


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon facebook GreyOrange Intuit Microsoft Նագարո
Դասավորություն Խանգարել դասավորում

Ենթադրենք, որ դուք ունեք ամբողջ թվերի զանգված: «Գտեք տրված զանգվածի համար բոլոր եզակի ենթաշարքերի գումարի հանրագումարը» խնդիրը պահանջում է պարզել բոլոր եզակի ենթատեսակների զանգվածների հանրագումարը (Ենթ զանգվածի գումարը յուրաքանչյուր ենթա-զանգվածի տարրերի հանրագումարն է):

Եզակի ենթ զանգվածի եզակի գումար ասելով ՝ մենք ուզում էինք ասել, որ ոչ մի ենթադաս չունի նույն արժեքը:

Օրինակ

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

Գտեք տրված զանգվածի համար բոլոր յուրահատուկ ենթադասերի զանգվածի գումարը

Ալգորիթմ

  1. Հայտարարել ա Քարտեզը.
  2. հավաքածու արտադրանք դեպի 0.
  3. Անցեք զանգվածը i = 0-ից մինչև i
    1. Սահմանեք գումար Ինչպես 0:
    2. Անցեք զանգվածը j = i- ից j
      • Գումարի մեջ գումարիր arr [j] արժեքը գումարի մեջ:
      • Քարտեզում ավելացրեք գումարը և դրա առաջացումը:
  4. Անցեք քարտեզը և ստուգեք այն բանալիների գրառումները, որոնց արժեքը 1 է:
    1. Արդյունքում ավելացրեք ստեղների արժեքը, երբ պայմանը բավարարված ենք համարում:
  5. Վերադարձի արդյունքը:

բացատրություն

Մեզ տրված է ամբողջ թիվ դասավորություն, Մեր խնդիրն է պարզել բոլոր եզակի ենթաշարքերի զանգվածը: Յուրաքանչյուր ենթ-զանգվածի գումարը կլինի յուրաքանչյուր ենթ-զանգվածի տարրի գումարը: Մենք պատրաստվում ենք օգտագործել ծիծաղել այս հարցը լուծելու համար: Մենք կվերցնենք զանգվածի յուրաքանչյուր տարր `նախապատկերացնելով գումարը 0-ի, երբ փոխենք i- ի արժեքը: Երբ մենք մտնում ենք ներքին օղակը, մենք կկողմնորոշենք մի զանգված i դեպի nև ավելացնել զանգվածի և գումարի յուրաքանչյուր արժեք: Դրանից հետո մենք միաժամանակ պահում ենք գումարը և դրա առաջացումը քարտեզում: Ամբողջ զանգվածն այցելելուց հետո պարզեք ենթաշղթաների հնարավոր բոլոր գումարը: Դրանից հետո մենք քարտեզում փնտրում ենք այն գումարները, որոնց առաջացումը միայն մեկ անգամ է: Քանի որ մենք ուզում ենք եզակի ենթաշարքերի զանգված, գումարներ, որոնք ունեն հստակ գումարներ: Այսպիսով, երբ քարտեզում գտնենք մեկ անգամ տեղի ունեցած գումարը, որը նշանակում է ասել, թե ում հաճախականությունը 1 է, մենք այդ գումարների արժեքը կավելացնենք արդյունքի մեջ:

Հաշվի առնելով դրա օրինակը.

Օրինակ

arr [] = {3, 1, 4, 5}

Նախ, մենք ունենք i = 0, ապա մենք ունենք 3 որպես տարր և մենք կսկսենք 3-ից, մենք գումարելու ենք 3-ը և թարմացնելու ենք 3-ը քարտեզի վրա, ապա ավելացնելով 1-ը գումարի մեջ և թարմացնելով 4-ը քարտեզում: , ապա գումարի մեջ որպես տարր վերցնելով 4-ը և քարտեզի վրա ավելացնելով 7-ը: Այսպիսով, մենք կավարտենք առաջին անցումը 5-ն այցելելուց և 12-ը քարտեզում թարմացնելուց հետո:

Այսպիսով, երբ մենք 4-ը որպես տարր վերցնենք և սկսենք 4-ից, մենք գումարը կթարմացնենք քարտեզի մեջ, քանի որ 4-ն արդեն Քարտեզը, մենք պարզապես կբարձրացնենք դրա հաճախականությունը և անտեսելու ենք այն գումարները, որոնց հաճախականությունը 1 չէ: Այսպիսով, մենք կկարողանանք կարգավորել եզակի ենթածրագրերը:

Կոդ

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

Java կոդ ՝ տրված զանգվածի բոլոր եզակի ենթադասերի զանգվածի գումարը գտնելու համար

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

Բարդության վերլուծություն

Timeամանակի բարդություն

Վրա2որտեղ «Ն» զանգվածում տարրերի քանակն է: Քանի որ մենք օգտագործել ենք 2 տեղադրված օղակ, իսկ գումարի որոնումը կատարվում է O (1) –ում ՝ օգտագործելով HashMap:

Տիեզերական բարդություն

Ո (n ^ 2) որտեղ «Ն» զանգվածի տարրերի քանակն է: Քանի որ վատագույն դեպքում մենք կարող ենք ունենալ n ^ 2 տարբեր ենթահաշիվների գումար: