סובאַררייַס מיט בוילעט עלעמענטן


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

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

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

בייַשפּיל

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

דערקלערונג: די אונטער-אַרייז זענען ⇒ (3, 1, 2), (3, 1), (1, 2), (2,1), (3), (1), (2), (1)

די גאַנץ לענג פון אַלע עלעמענטן זענען (3 + 2 + 2 + 2 + 1 + 1 + 1 + 1) = 10.

סובאַררייַס מיט בוילעט עלעמענטן

arr[] = {3, 5, 8, 9}
20

דערקלערונג: די סאַב-ערייז זענען ⇒ (3), (5), (8), (9), (3, 5), (5, 8), (8, 9), (3, 5, 8), (5, 8, 9), (3, 5, 8, 9)

די גאַנץ לענג פון אַלע עלעמענטן זענען (1 + 1 + 1 + 1 + 2 + 2 + 2 +3 +3 +4) = 10.

אַלגערידאַם צו געפֿינען סובאַררייַס מיט פאַרשידענע עלעמענטן

1. Declare a map.
2. Set output and j to 0.
3. Traverse the array from i=0 to i<n(length of an array).
  1. While j is less than n and if a set doesn’t contain the value of arr[j].
    1. Insert all the values of arr [j].
  2. Update the output to output +=((j - i) * (j - i + 1))/2.
  3. Remove the arr[i] from Set.
4. Return output.

דערקלערונג

מיר האָבן געגעבן אַן ינטעגער מענגע. אונדזער אַרבעט איז צו געפֿינען די סומע פון ​​די לענג פון אַלע די סאַב-ערייז וואָס זענען קאַנטיגיואַס און בלויז האָבן בוילעט עלעמענטן. מיר וועלן נוצן אַ שטעלן. שטעלן גיט אַ שטריך פון באַזייַטיקונג פון קאַפּיד אָדער פּראָסט עלעמענטן פֿון אַ סכום. שטעלן j צו 0 און רעזולטאַט צו 0.

אָנהייב דורך דורך די מענגע און נוצן אַ בשעת שלייף. באַשטעטיק די ווערט פון j צו 0 און אינעווייניק בשעת שלייף מיר וועלן אַריבער די שלייף בשעת ינקראַמענטינג דזש. שטעלן עטלעכע באדינגונגען אויף אים, בשעת j איז ווייניקער ווי n, ד"ה די לענג פון די מענגע און אויך אויב עס איז געפֿונען אַז באַשטעטיקט כּולל די ווערט פון אַרר [j]. זאל אונדז באַטראַכטן אַ בייַשפּיל:

Arr [] = {3, 1, 2, 1}

מיר וועלן דורכפאָר די מענגע פּיקינג יעדער עלעמענט אין איין מאָל, רעכן מיר וועלן סעלעקטירן 3 אין די ערשטער מאָל, אין אַרר [דזש], געדאַנק איז צו האַלטן די ויסווייניקסט שלייף קעסיידערדיק נאָר פֿאַר אַ בשעת דעם 3 וועט אָנהייבן אין בשעת שלייף, ווי j איז יניטיאַליזעד ווי 0, און סעט כּולל 3 פֿאַר די ערשטער מאָל, אַזוי עס וועט אַרייַן אין a בשעת שלייף און אַרייַן די אַרר [j] מיטל 3 און פאַרגרעסערן די j ++, עס וועט קלייַבן ווייַטער עלעמענט ווי 1, שטעלן קען נישט אַנטהאַלטן עס אַזוי עס וועט זיין ינסערטאַד אין אַ גאַנג, דערנאָך קומט 2 און דערנאָך קומט 1, אָבער דאָס מאָל, 1 איז שוין אין די שלייף אַזוי עס וועט קומען אויס פון די בשעת שלייף.

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

קאָדעקס

C ++ צו געפֿינען סובאַררייַס מיט פאַרשידענע עלעמענטן

#include<iostream>
#include<unordered_set>

using namespace std;

int getLength(int arr[], int n)
{
    unordered_set<int> SET;

    int j = 0, output = 0;
    for (int i=0; i<n; i++)
    {
        while (j < n && SET.find(arr[j]) == SET.end())
        {
            SET.insert(arr[j]);
            j++;
        }
        output += ((j - i) * (j - i + 1))/2;
        SET.erase(arr[i]);
    }
    return output;
}
int main()
{
    int arr[] = {3, 1, 2, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << getLength(arr, n);
    return 0;
}
13

Java קאָד צו געפֿינען סובאַררייַס מיט פאַרשידענע עלעמענטן

import java.util.Set;
import java.util.HashSet;

class LengthOfDistinctElements
{
    public static int getLength(int[] arr, int n)
    {
        Set<Integer> SET = new HashSet<>();
        int j = 0, output = 0;
        for (int i = 0; i < n; i++)
        {
            while (j < n && !SET.contains(arr[j]))
            {
                SET.add(arr[j]);
                j++;
            }
            output += ((j - i) * (j - i + 1)) / 2;
            SET.remove(arr[i]);
        }
        return output;
    }
    public static void main(String[] args)
    {
        int[] arr = { 3, 1, 2,1  };
        int n = arr.length;
        System.out.println(getLength(arr, n));
    }
}
13

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

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

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

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

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