געפֿינען אויב עס איז אַ סובאַרראַ מיט 0 סומע


שוועריקייט לעוועל מיטל
אָפט געבעטן אין סיטריקס DE שאָ גאָלדמאַן סאַקס טאקע MakeMyTrip OYO רומז Paytm טקס
מענגע האַש

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

בייַשפּיל

געפֿינען אויב עס איז אַ סובאַרראַ מיט 0 סומע

arr[] = {2,1,-3,4,5}
yes

דערקלערונג

דאָ, עלעמענטן פֿון אינדעקס 0-2 האָבן אַ סומע 0.

arr[] = {4,1,-4,5,1}
yes

דערקלערונג

קיין סאַב-מענגע יגזיסץ אַז סומע 0.

אַלגאָריטהם

  1. דערקלערן א שטעלן.
  2. Initialize סאַכאַקל צו קסנומקס.
  3. אַריבער די מענגע, בשעת i <n (לענג פון די מענגע).
    1. לייג סומע צו אַרר [i] און קראָם עס צו סאַכאַקל.
    2. קוק אויב די פאלגענדע באדינגונגען זענען אמת:
      1. סאַכאַקל == 0 / אַרר [איך] == 0 / אויב באַשטעטיקט כּולל די ווערט פון סאַכאַקל.
      2. אויב אמת, דעמאָלט צוריקקומען אמת.
    3. לייג די סומע צו די שטעלן.
  4. צוריק פאַלש.

דערקלערונג

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

אויב קיינער פון די סאַב-ערייז איז סאַכאַקל 0, מיר וועלן צוריקקומען פאַלש פון די שלייף. עס איז אויך איין זאַך, אויב איינער פון אַן עלעמענט איז 0, מיר וועלן אויך צוריקקומען אמת ווייַל אַן עלעמענט זיך איז אַ סאַב-מענגע פון ​​איין עלעמענט. אַזוי עס מיטל אַז מיר געפונען איין אַזאַ סאַב-מענגע.

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

לאָמיר באַטראַכטן אַ ביישפּיל:

בייַשפּיל

אַרר [] = {- 3,2,1,9,6}

דאָ אין די קאָד, מיר וועלן אַריבער אַ מענגע און לייגן סומע און אַרר [i] און סטאָרד אין סאַכאַקל און נאָך אַז קאָנטראָלירונג, אויב סומע == 0 אָדער אַרר [i] איז גלייַך צו 0 אָדער באַשטעטיקט כּולל די ווערט פון סאַכאַקל, אויב איינער פון די געגעבן צושטאַנד איז צופֿרידן, מיר וועלן צוריקקומען אמת און דעריבער לייגן סומע אין סעט.

אויב קיין פון די סאַב-מענגע געפונען, מיר וועלן צוריקקומען פאַלש.

סומע = 0, שטעלן = {}

איך = 0, אַרר [איך] = -3

סאַכאַקל = סאַכאַקל + אַרר [איך] => 0 + - 3 = -3

אויב סומע == 0 אָדער אַרר [i] איז גלייַך צו 0 אָדער סעט כּולל די ווערט פון סאַכאַקל, דריי פון זיי זענען פאַלש, אַזוי מיר טאָן גאָרנישט דאָ און לייגן -3 אין סעט.

איך = 1, אַרר [איך] = 2

סאַכאַקל = סאַכאַקל + אַרר [איך] => -3 + 2 = -1

אויב סומע == 0 אָדער אַרר [i] איז גלייַך צו 0 אָדער סעט כּולל די ווערט פון סאַכאַקל, דריי פון זיי זענען פאַלש, אַזוי מיר טאָן גאָרנישט דאָ און לייגן -1 אין סעט.

איך = 2, אַרר [איך] = 1

סאַכאַקל = סאַכאַקל + אַרר [איך] => -1 + 1 = 0

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

רעזולטאַט: יאָ, אַ סאַב-מענגע מיט סומע 0 יגזיסץ.

קאָדעקס

C + + קאָד צו געפֿינען אויב עס איז אַ סובאַררייַ מיט 0 סומע

#include<iostream>
#include<unordered_set>

using namespace std;

bool isSubArrayZero(int arr[], int n)
{
    unordered_set<int> Set;
    int sum = 0;
    for (int i = 0 ; i < n ; i++)
    {
        sum += arr[i];
        if (sum == 0 || Set.find(sum) != Set.end())
            return true;

        Set.insert(sum);
    }
    return false;
}
int main()
{
    int arr[] = {-3, 2, 1, 9, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    if (isSubArrayZero(arr, n))
        cout << "Yes, a sub-array with sum 0 exist";
    else
        cout << "No, a sub-array with sum 0 does not exist";
    return 0;
}
Yes, a sub-array with sum 0 exist

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

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

class sumOfSubArrayZero
{
    public static Boolean isSubArrayZero(int arr[])
    {
        Set<Integer> set = new HashSet<Integer>();
        int Sum = 0;
        for (int i = 0; i < arr.length; i++)
        {
            Sum += arr[i];
            if (arr[i] == 0 || Sum == 0 || set.contains(Sum))
                return true;

            set.add(Sum);
        }
        return false;
    }
    public static void main(String arg[])
    {
        int arr[] = {-3, 2, 1, 9, 6};
        if (isSubArrayZero(arr))
            System.out.println("Yes, a subarray with sum 0 exists");
        else
            System.out.println("No, a subarray with sum 0 does not exist");
    }
}
Yes, a subarray with sum 0 exists

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

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

אָ (N) ווו “N” איז די נומער פון עלעמענטן אין די מענגע. דאָס אַלץ איז געווען מעגלעך ווייַל פון אַ HashSet ווייַל עס אַלאַוז אונדז צו טאָן ינסערט, זוכן, ויסמעקן אין אָ (1) צייט.

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

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