קאָנטיגואָוס אַררייַ לעעטקאָדע


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

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

"קאָנטיגואָוס אַררייַ לעעטקאָדע" פּראָבלעם שטאַטן אַז איר באַקומען אַן מענגע אַ [] פון גרייס n באשטייט בלויז פון 1 און 0. געפֿינען די לאָנגעסט סובאַררייַ אין וואָס די נומער פון 1 איז גלייַך צו די נומער פון 0 ס.

בייַשפּיל

קאָנטיגואָוס אַררייַ לעעטקאָדע

a[ ] = {1, 0, 1, 1, 1, 0, 0}
1 to 6

דערקלערונג: טשוזינג אַ סובאַררייַ פון אינדעקס 1 צו 6 גיט אונדז דער בעסטער רעזולטאַט פון לענג 6. די קאַנטיגיואַס מענגע פון ​​1 צו 6 אינדעקס האט 3 זעראָס און 3 אָנעס. דאָ מיר האָבן באטראכט 0 באזירט ינדעקסינג.

a[ ] = {1, 1}
No such subarray

צוגאַנג

נאַיוו מעטאַד

גענעראַטע אַלע מעגלעך סובאַררייַס. קאָנטראָלירן אויב עס יגזיסץ קיין סובאַרראַי וואָס די נומער פון 1 איז גלייַך ווי די נומער פון 0 ס. מיר נוצן צוויי פּוינטערז i און j פֿאַר די לינקס און רעכט גרענעץ פון אַ סובאַרראַ. דערנאָך מיר קאָנטראָלירן אויב די סומע פון ​​סובאַררייַ פון i צו j האט סומע = 0, נאָך ריפּלייסינג 0 מיט -1. אויב דאָס איז אמת, מיר האָבן געפֿונען אַ סובאַררייַ וואָס באַפרידיקן די באדינגונגען. איצט מיר דערהייַנטיקן אונדזער ענטפער.

אַלגערידאַם פֿאַר קאַנטיגיואַס מענגע לעעטקאָדע פּראָבלעם

1. Initialize a binary array a[] of size n and three variables sum, max=-1, and start.
2. Traverse through the array and update sum as -1 if a[i] is 0 else 1.
3. Traverse the inner loop and add -1 in sum if a[i] is 0 else 1.
4. Check if the sum is 0 and max is less than j-i+1, update max as j-i+1 and start as i.
5. Outside the loops check if max is -1 print "No such subarray" else print starting and ending index.

קאָדעקס

C ++ פּראָגראַם צו סאָלווע קאָנטיגואָוס ערי לעעטקאָדע פּראָבלעם
#include <bits/stdc++.h> 
using namespace std; 
  
int subArray(int a[], int n){ 
    int sum = 0; 
    int max = -1, start; 
  
    for(int i=0; i<n-1; i++){ 
        sum = (a[i]==0) ? -1 : 1; 
  
        for(int j=i+1; j<n; j++){ 
            (a[j]==0) ? (sum+=-1) : (sum+=1); 
  
            if(sum == 0 && max < j-i+1){ 
                max = j-i+1; 
                start = i; 
            } 
        } 
    } 
    if(max == -1) 
        cout<<"No such subarray"; 
    else
        cout<<start<<" to "<<start+max-1; 
  
    return max; 
} 
  
int main(){ 
    int a[] = { 1, 0, 1, 1, 1, 0, 0 }; 
    int n = sizeof(a) / sizeof(a[0]); 
  
    subArray(a, n); 
    return 0; 
}
1 to 6
דזשאַוואַ פּראָגראַם צו סאָלווע קאָנטיגואָוס ערי לעעטקאָדע פּראָבלעם
class LongestSubArray{
    int subArray(int a[], int n){ 
        int sum = 0; 
        int max = -1, start=0,end=0; 
        
        for(int i=0; i<n-1; i++){ 
            sum = (a[i]==0) ? -1 : 1; 
            
            for(int j=i+1; j<n; j++){ 
                if(a[j] == 0) 
                    sum += -1; 
                else
                    sum += 1;  
                
                if(sum == 0 && max < j-i+1){ 
                    max = j-i+1; 
                    start = i; 
                } 
            } 
        } 
        if(max == -1) 
            System.out.println("No such subarray");
        else
            end = start+max-1;
            System.out.println(start+" to "+end);
        
        return max; 
    } 
    public static void main(String[] args){ 
        LongestSubArray s = new LongestSubArray(); 
        int a[] = { 1, 0, 1, 1, 1, 0, 0 }; 
        int n = a.length; 
        
        s.subArray(a, n); 
    } 
}
1 to 6

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

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

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

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

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

ניצן האַש מאַפּע

אַלגערידאַם פֿאַר קאַנטיגיואַס מענגע לעעטקאָדע פּראָבלעם

1. Initialize a binary array a[] of size n.
2. Initialize an unordered map.
3. Traverse through the array and update the array value of the current index as -1 if current value if 0 else 1.
4. Traverse through the array and add the elements.
5. If the sum is 0, update max as i+1 and end as i.
6. Else Traverse map and update max as i - map(sum+n) and end as i if max is less than i - map(sum+n) else update map(sum+n) as i.
7. Traverse through the array and update the array value of the current index as 0 if current value is -1 else 1.
8. If the end is greater than -1 print starting and ending index.
9. Else print "No such subarray".

וואָס מיר האָבן געטאן דאָ, נאָר ווען מיר דאַרפֿן צו געפֿינען די גרעסטע סובאַרראַיע מיט סומע 0. וואָס מיר טאָן איז צו נעמען די פּרעפיקס סומע און טשעק אין אונדזער מאַפּע אויב עס איז ערגעץ ווו מיר קענען געפֿינען די זעלבע סומע. דערנאָך די סובאַרראַי סטאַרטינג פון די ווערט סטאָרד אין מאַפּע +1 צו די קראַנט אינדעקס איז סאַכאַקל 0. דאָ, מיר נוצן (סומע + n) ווי דער שליסל. אָבער מיר קען אויך נוצן די סומע גלייַך. אָבער אויב מיר נוצן (sum + n) ווי אַ שליסל, מיר קענען אויך נוצן אַ מענגע אַנשטאָט פון אַ HashMap. ווייַל מיר קענען פאַרזיכערן אַז (סומע + n)> = 0 און מענגע ינדעקסינג אָנהייבן פֿון 0.

קאָדעקס

C ++ פּראָגראַם צו סאָלווע קאָנטיגואָוס ערי לעעטקאָדע פּראָבלעם
#include <bits/stdc++.h> 
using namespace std; 
  
int subArray(int a[], int n){ 
    
    unordered_map<int, int> hM; 
  
    int sum = 0, max = 0, end = -1; 
  
    for(int i=0; i<n; i++) 
        a[i] = (a[i] == 0) ? -1 : 1; 
  
    for(int i=0; i<n; i++){ 
        sum += a[i]; 
  
        if(sum == 0){ 
            max = i + 1; 
            end = i; 
        } 
  
        if(hM.find(sum + n) != hM.end()){ 
            if(max < i - hM[sum + n]){ 
                max = i - hM[sum + n]; 
                end = i; 
            } 
        } 
        else 
            hM[sum + n] = i; 
    } 
  
    for(int i=0; i<n; i++) 
        a[i] = (a[i] == -1) ? 0 : 1; 
        
    if(end>-1)
        cout<<end - max + 1<<" to "<<end; 
    else
        cout<<"No such subarray";
    return max; 
} 
  
int main(){ 
    int a[] = {1, 0, 1, 1, 1, 0, 0}; 
    int n = sizeof(a) / sizeof(a[0]); 
  
    subArray(a, n); 
    return 0; 
} 
1 to 6
דזשאַוואַ פּראָגראַם צו סאָלווע קאָנטיגואָוס ערי לעעטקאָדע פּראָבלעם
import java.util.HashMap;

class LongestSubArray{
    int subArray(int a[], int n){ 
        
        HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>(); 
  
        int sum = 0, max = 0, end = -1, start = 0; 
  
        for(int i=0; i<n; i++){ 
            a[i]=(a[i]==0) ? -1 : 1; 
        } 
  
        for(int i=0; i<n; i++){ 
            sum += a[i]; 
  
            if(sum == 0){ 
                max = i + 1; 
                end = i; 
            } 
  
            if(hM.containsKey(sum + n)){ 
                if(max < i - hM.get(sum + n)){ 
                    max = i - hM.get(sum + n); 
                    end = i; 
                } 
            } 
            else 
                hM.put(sum + n, i); 
        } 
  
        for(int i=0; i<n; i++) { 
            a[i] = (a[i] == -1) ? 0 : 1; 
        } 
  
        int index = end - max + 1; 
        
        if(end>-1)
            System.out.println(index + " to " + end); 
        else
            System.out.println("No such subarray"); 
        return max;  
    } 
    public static void main(String[] args){ 
        LongestSubArray s = new LongestSubArray(); 
        int a[] = { 1, 0, 1, 1, 1, 0, 0 }; 
        int n = a.length; 
        
        s.subArray(a, n); 
    } 
}
1 to 6

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

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

אָ (N) ווו n איז די נומער פון עלעמענטן אין דער געגעבן מענגע אַ []. זינט E געניצט ונאָרדערעד_מאַפּ / האַשמאַפּ, מיר זענען ביכולת צו דערגרייכן אָ (ען) צייט ווייַל האַשמאַפּ אַלאַוז אָ (1) צייט צו דורכפירן ינסערשאַן שאַרף, דילישאַן.

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

אָ (N) ווייַל מיר געוויינט N עקסטרע פּלאַץ. זינט מיר געוויינט אַ HashMap אַד סטאָרד די אינפֿאָרמאַציע וועגן N עלעמענטן, אין די ערגסט פאַל, עס קען זיין N יסודות.