Գտեք, եթե կա ենթագոտի ՝ 0 գումարով


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Citrix ԴԵ Շոուն Goldman Sachs-ը Իսկապես MakeMyTrip- ը OYO սենյակներ Paytm TCS
Դասավորություն Խանգարել

«Գտեք, եթե գոյություն ունի ենթագոտի 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 գումար Ինչպես 0:
  3. Անցեք զանգվածը, մինչդեռ ես <n (զանգվածի երկարությունը):
    1. Ar- ին գումարել գումար [i] և պահպանել այն գումարելու համար:
    2. Ստուգեք արդյոք հետևյալ պայմաններից որևէ մեկը ճիշտ է.
      1. sum == 0 / arr [i] == 0 / եթե Set պարունակում է գումարի արժեք:
      2. եթե ճշմարիտ է, ապա վերադարձիր ճշմարիտ:
    3. Գումարն ավելացնել հավաքածուի մեջ:
  4. Վերադարձեք կեղծ:

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

Մենք ստացանք խնդրի հայտարարություն, որը խնդրում է պարզել, արդյոք գոյություն ունի որևէ ենթա-զանգված `0.-ի հավասար գումարով: Դա լուծելու համար մենք կօգտագործենք բազմություն` այս խնդիրը լուծելու համար: Մենք պատրաստվում ենք տվյալ զանգվածի տարրերը պահել հավաքածուի մեջ: Դրանից հետո միաժամանակ գումարն ավելացրեք գումարի մեջ և ստուգեք, արդյոք առկա է ենթախմբի որևէ համընկնում հավաքածուում ընթացիկ գումարի հետ, թե՞ գումարը ինքնին հավասար է 0. Եթե պարզվի, որ ենթագոտում կա 0 գումարով, ապա մենք կվերադառնանք ճիշտ.

Եթե ​​ենթածրագրերից և ոչ մեկում չի հայտնաբերվել 0 գումար, ապա մենք պատրաստվում ենք կեղծը դուրս բերել օղակից: Բացի այդ, կա մեկ բան, եթե տարրերից որևէ մեկը 0 է, ապա մենք նույնպես կվերադառնանք ճշմարիտ, քանի որ տարրն ինքնին մեկ առանձին տարրի ենթախաղ է: Այսպիսով, դա նշանակում է, որ մենք գտել ենք մեկ այդպիսի ենթ-զանգված:

Այստեղ ծածկագրում մենք հայտարարում ենք Բուլյան գործառույթ, այն կվերադառնա կամ ճիշտ կամ կեղծ, եթե ենթաբազմությունը գտնվի, այն կվերադառնա ճշմարիտ, հակառակ դեպքում կվերադառնա կեղծ:

Քննենք մի օրինակ.

Օրինակ

arr [] = {- 3,2,1,9,6}

Այստեղ ծածկագրում մենք կքննարկենք զանգվածը և կավելացնենք գումար և ar [i] և կպահենք գումարի մեջ, իսկ այդ ստուգումից հետո, եթե sum == 0 կամ arr [i] հավասար է 0-ի կամ Set պարունակում է գումարի արժեք, եթե տրված պայմաններից որևէ մեկը բավարարված է, ապա մենք պատրաստվում ենք վերադառնալ ճշմարիտ և այնուհետև գումար գումարել Սահմանել:

Եթե ​​ենթադասերից ոչ մեկը չգտնվի, մենք կվերադառնանք կեղծ:

գումար = 0, Սահմանել = {}

i = 0, arr [i] = -3

գումար = գումար + ar [i] => 0 + - 3 = -3

եթե sum == 0 կամ arr [i] հավասար է 0-ի կամ Set- ը պարունակում է գումարի արժեք, դրանցից երեքը կեղծ են, ուստի մենք այստեղ ոչինչ չենք անում և -3-ը ավելացնում ենք Set- ի:

i = 1, arr [i] = 2

գումար = գումար + ar [i] => -3 + 2 = -1

եթե sum == 0 կամ arr [i] հավասար է 0-ի կամ Set- ը պարունակում է գումարի արժեք, դրանցից երեքը կեղծ են, ուստի մենք այստեղ ոչինչ չենք անում և -1-ը ավելացնում ենք Set- ի:

i = 2, arr [i] = 1

գումար = գումար + ar [i] => -1 + 1 = 0

եթե գումարը == 0 պայմանը բավարարված է այստեղ, ուստի մենք վերադառնում ենք true, դա նշանակում է, որ մենք գտել ենք ենթ գումարած 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

Java կոդ ՝ 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

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

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

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է: Այս ամենը հնարավոր էր HashSet- ի օգտագործման պատճառով, քանի որ այն թույլ է տալիս մեզ ներդնել, որոնել, ջնջել O (1) ժամանակում:

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

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է: Քանի որ ստեղծված հեշ հավաքածուում կարող է լինել առավելագույնը n տարր, տարածության բարդությունը գծային է: