ציילן סובאַררייַס מיט גאַנץ בוילעט עלעמענטן זעלביקער ווי אָריגינעל מענגע


שוועריקייט לעוועל מיטל
אָפט געבעטן אין אַמאַזאָן דאַטאַבריקס Fab האָנייוועלל PayU קוואַדראַט טעראַדאַטאַ יאַנדעקס
מענגע האַש האַשינג סליידינג ווינדאָו

פּראָבלעם סטאַטעמענט

"ציילן סובאַררייַס מיט גאַנץ בוילעט עלעמענטן זעלביקער ווי אָריגינעל מענגע”שטאַטן אַז איר באַקומען אַ ינטאַדזשער מענגע. די פּראָבלעם ויסזאָגונג פרעגט צו געפֿינען די גאַנץ נומער פון סאַב-ערייז וואָס אַנטהאַלטן אַלע בוילעט עלעמענטן ווי אין אַן אָריגינעל מענגע.

בייַשפּיל

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

דערקלערונג: אונטער-מעריע ⇒ {2, 1, 3}, {1, 3, 2}, {1, 3, 2, 3}, {2, 1, 3, 2} און {2, 1, 3, 2 , 3} אַנטהאַלטן אַלע בוילעט עלעמענטן ווי אָריגינעל מענגע.

ציילן סובאַררייַס מיט גאַנץ בוילעט עלעמענטן זעלביקער ווי אָריגינעל מענגע

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

דערקלערונג: אונטער-מעריע ⇒ {3, 4, 1, 2}, {4, 3, 4, 1, 2}, {2, 4, 3, 4, 1} און {2, 4, 3, 4, 1 , 2} אַנטהאַלטן אַלע בוילעט עלעמענטן ווי אָריגינעל מענגע.

אַלגערידאַם צו ציילן סובאַררייַס מיט גאַנץ בוילעט עלעמענטן זעלביקער ווי אָריגינעל מענגע

1. Declare a map.
2. Add all the values of array into the map with 1 as each key’s value.
3. Find the size of the map, store it to k and clear the map.
4, Set output, right, and maxsa to 0.
5. Traverse the array, from i=0, to i < n(length of the array).
  1. While the right is less than n and maxsa is less than k,
    1. Insert arr[right] and increase its frequency by 1.
    2. Check if the map’s value of current array element (arr[right]) is equal to 1 if true then increase the count of maxsa by 1.
  2. Increase the count of right by 1.
  3. If maxsa is equal to k, then update output à output += (n - right + 1).
  4. Insert the value of current arr[left] and decrease its frequency by 1.
  5. If the map’s arr[left] is equal to 0, then decrease the value of maxsa by 1.
6. Return output.

דערקלערונג

מיר האָבן געגעבן אַן ינטעגער מעניו, מיר זענען געבעטן צו געפֿינען אויס די גאַנץ נומער פון סאַב-ערייז וואָס אַנטהאַלטן אַלע באַזונדער עלעמענטן ווי עס זענען פאָרשטעלן אין אַן אָריגינעל מענגע. פֿאַר דעם, מיר וועלן נוצן האַשינג. עס איז אַ עפעקטיוו צוגאַנג צו סאָלווע דעם קאָד.

דערקלערן א מאַפּע. מיר וועלן דורכגיין די גאנצע מענגע און שטעלן יעדער עלעמענט אין די מאַפּע מיט בלויז אַ אָפטקייט פון 1. ווייַל מיר טאָן נישט וועלן צו ציילן די אָפטקייַט פון יעדער עלעמענט. דאָס איז נאָר צו וויסן ווי פילע יינציק שליסלען זענען פאָרשטעלן אין אַ געגעבן מענגע. מיר וועלן קראָם די גרייס פון די מאַפּע אין די בייַטעוודיק k און ויסמעקן די מאַפּע.

מיר וועלן אַריבער די גאנצע מענגע. אבער פאר דעם, מיר שטעלן די ווערט פון רעזולטאַט, רעכט און מאַקססאַ צו 0. סטאַרטינג פון 0, מיר וועלן אַרייַן ווידער אין אַ שלייף אין זוכן פון אַ סאַב-מענגע, בשעת די רעכט איז ווייניקער ווי n און מאַקססאַ איז ווייניקער ווי ק. איצט מיר שטעלן די מענגע עלעמענט און פאַרגרעסערן די אָפטקייַט פון 1. מיר וועלן קאָנטראָלירן אויב די קראַנט עלעמענט האט אַ אָפטקייַט פון 1. אָדער מיר נאָר דערהייַנטיקט עס צו מער פון וואָס, אויב עס איז אמת, דאַן פאַרגרעסערן די ווערט פון maxsa.

נאָך קומען אויס פון די בשעת שלייף, איר וועט האָבן אַ ינקראַמענדיד ווערט פון מאַקססאַ, אויב עס איז גלייַך צו ק, דערהייַנטיקן דער רעזולטאַט צו N- רעכט +1. ווי מיר שוין שטעלן די וואַלועס פון מענגע עלעמענט אין דער מאַפּע. מיר וועלן איצט פאַרקלענערן די אָפטקייַט פון 1 און קאָנטראָלירן אויב ער [לינקס] ווערט איז 0 און פאַרקלענערן די מאַקסאַ ווערט. ווען מיר געפֿונען די ווערט פון maxsa צו k, מיר דערהייַנטיקן די רעזולטאַט ווערט.

קאָדעקס

C ++ קאָד צו ציילן סובאַררייַס מיט גאַנץ בוילעט עלעמענטן ווי אָריגינעל מענגע

#include<iostream>
#include<unordered_map>

using namespace std;

int getSubArrayDistinct(int arr[], int n)
{
    unordered_map<int, int> MAP;
    for (int i = 0; i < n; ++i)
        MAP[arr[i]] = 1;

    int k = MAP.size();

    MAP.clear();

    int output = 0, right = 0, maxsa = 0;
    for (int left = 0; left < n; ++left)
    {
        while (right < n && maxsa < k)
        {
            ++MAP[ arr[right] ];

            if (MAP[ arr[right] ] == 1)
                ++maxsa;

            ++right;
        }
        if (maxsa == k)
        {
            output += (n - right + 1);
        }
        --MAP[ arr[left] ];

        if (MAP[ arr[left] ] == 0)
        {
            --maxsa;
        }
    }
    return output;
}
int main()
{
    int arr[] = {2, 1, 3, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << getSubArrayDistinct(arr, n);
}
5

ז'אבא קאָד צו ציילן סובאַראַריעס מיט גאַנץ בוילעט עלעמענטן ווי אָריגינעל מענגע

import java.util.HashMap;

class SubarrayWithDistinctEle
{
    public static int getSubArrayDistinct(int arr[], int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<Integer,Integer>()
        {
            @Override
            public Integer get(Object key)
            {
                if(!containsKey(key))
                    return 0;
                return super.get(key);
            }
        };

        for (int i = 0; i < n; ++i)
            MAP.put(arr[i], 1);
        int k = MAP.size();

        MAP.clear();

        int output = 0, right = 0, maxsa = 0;
        for (int left = 0; left < n; ++left)
        {
            while (right < n && maxsa < k)
            {
                MAP.put(arr[right], MAP.get(arr[right]) + 1);

                if (MAP.get(arr[right])== 1)
                {
                    ++maxsa;
                }

                ++right;
            }
            if (maxsa == k)
            {
                output += (n - right + 1);
            }

            MAP.put(arr[left], MAP.get(arr[left]) - 1);

            if (MAP.get(arr[left]) == 0)
                --maxsa;
        }
        return output;
    }
    public static void main(String args[])
    {
        int arr[] = {2, 1, 3, 2, 3};
        int n=arr.length;
        System.out.println(getSubArrayDistinct(arr, n));
    }
}
5

קאַמפּלעקסיטי אַנאַליסיס

צייט קאַמפּלעקסיטי

אָ (N) ווו "N" איז די נומער פון עלעמענטן אין די מענגע. זינט מיר האָבן דורכגעקאָכט די מענגע און געוויינט האַשמאַפּ, וואָס האָט געמאכט אונדז דערגרייכן לינעאַר צייט קאַמפּלעקסיטי.

ספעיס קאַמפּלעקסיטי

אָ (N) ווו "N" איז די נומער פון עלעמענטן אין די מענגע. ווייַל מיר האָבן געוויינט אַ מענגע צו קראָם די ינפּוט און אַ HashMap וואָס וועט קראָם N עלעמענטן. אזוי אַטשיווד לינעאַר פּלאַץ קאַמפּלעקסיטי.