0 нийлбэр бүхий дэд массив байгаа эсэхийг олоорой


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Citrix DE Шоу Goldman Sachs Үнэндээ MakeMyTrip OYO өрөөнүүд Paytm холболтуудын
Array Хаш

“0 сумтай дэд массив байгаа эсэхийг олоорой” гэсэн бодлогод танд ан өгөгдсөн болно бүхэл тоо массив сөрөг бүхэл тоонуудыг агуулна. Асуудлын шийдэл нь дор хаяж 1 хэмжээтэй дэд массив байгаа эсэхийг тодорхойлохыг хүсдэг. Энэ дэд массив нь 1-тэй тэнцүү нийлбэртэй байх ёстой.

Жишээ нь

0 нийлбэр бүхий дэд массив байгаа эсэхийг олоорой

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

Тайлбар

Энд 0-ээс 2-р индексийн элементүүд 0-ийн нийлбэртэй байна.

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

Тайлбар

0 нийлбэртэй дэд массив байхгүй байна.

Алгоритм

  1. Мэдүүлэх a нь чансаанд.
  2. Эхлүүлэх нийлбэр 0 рүү.
  3. Массивыг дайран өнгөрөх би <n (массивын урт).
    1. Arr [i] дээр нийлбэр нэмж, нийлбэрт хадгална.
    2. Дараах нөхцлүүдийн аль нэг нь үнэн эсэхийг шалгана уу.
      1. sum == 0 / arr [i] == 0 / Хэрэв Set нь нийлбэрийн утгыг агуулсан бол.
      2. хэрэв үнэн бол үнэнийг буцаа.
    3. Нийлбэрийг Set дээр нэмнэ үү.
  4. Худал буцаах.

Тайлбар

0-тэй тэнцүү нийлбэр бүхий дэд массив байгаа эсэхийг тодруулах гэсэн асуудлын хариуг авлаа. Үүнийг шийдэхийн тулд Set асуудлыг ашиглан энэ асуудлыг шийднэ. Бид өгөгдсөн массивын элементүүдийг Set дотор хадгалах болно. Дараа нь утгыг нийлбэр дээр нэмээд олонлогийн одоогийн нийлбэртэй тохирох дэд массив байгаа эсэхийг эсвэл нийлбэр нь 0-тэй тэнцүү байгаа эсэхийг шалгана уу. Хэрэв 0-ийн нийлбэртэй дэд массив байх нь тогтоогдвол бид буцах болно. үнэн.

Хэрэв дэд массивуудын аль нь ч 0-тэй гэж тогтоогдохгүй бол бид циклээс худал утгыг буцааж өгөх болно. Түүнчлэн, нэг зүйл байна, хэрэв элементийн аль нэг нь 0 байвал элемент нь өөрөө нэг элементийн дэд массив тул бид үнэн болно. Тиймээс бид ийм дэд массивыг олсон гэсэн үг юм.

Энд кодод бид Boolean функцийг зарлаж байгаа бөгөөд энэ нь үнэн эсвэл худал гэсэн утгатай, дэд массив олдсон тохиолдолд үнэн, өөрөөр буцаах болно.

Нэг жишээг авч үзье.

Жишээ нь

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

Энд код дээр бид массивыг дайран өнгөрч, sum ба arr [i] -г нэмж, нийлбэрт хадгална, хэрэв дараа нь sum == 0 эсвэл arr [i] нь 0-тэй тэнцүү эсвэл Set нь нийлбэрийн утгыг агуулсан бол Хэрэв өгөгдсөн нөхцлүүдийн аль нэг нь хангагдсан бол бид үнэнийг буцааж дараа нь нийлбэрийг Set болгон нэмнэ.

Хэрэв дэд массивын аль нь ч олдохгүй бол бид false гэсэн утгатай буцах болно.

sum = 0, Set = {}

i = 0, arr [i] = -3

sum = sum + arr [i] => 0 + - 3 = -3

хэрэв sum == 0 эсвэл arr [i] нь 0-тэй тэнцүү эсвэл Set нь нийлбэрийн утгыг агуулсан бол гурвуулаа худлаа тул бид энд юу ч хийхгүй ба Set-д 3 нэмнэ.

i = 1, arr [i] = 2

sum = sum + arr [i] => -3 + 2 = -1

хэрэв sum == 0 эсвэл arr [i] нь 0-тэй тэнцүү эсвэл Set нь нийлбэрийн утгыг агуулсан бол гурвуулаа худлаа тул бид энд юу ч хийхгүй ба Set-д 1 нэмнэ.

i = 2, arr [i] = 1

sum = sum + arr [i] => -1 + 1 = 0

хэрэв нийлбэр == 0 нөхцөл энд хангагдсан тул бид үнэн гэсэн утгатай бол бид 0 нийлбэртэй дэд массив олсон гэсэн үг юм.

Гаралт: Тийм ээ, 0 нийлбэр бүхий дэд массив байна.

код

0 нийлбэр бүхий дэд массив байгаа эсэхийг олох C ++ код

#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-ийн дэд массив байгаа эсэхийг олох Java код

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

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N) хаана "N" нь массив дахь элементүүдийн тоо юм. Энэ бүхэн нь H (S) хугацаанд оруулах, хайх, устгах боломжийг бидэнд олгодог тул HashSet-ийг ашигласнаар боломжтой болсон.

Сансрын нарийн төвөгтэй байдал

O (N) хаана "N" нь массив дахь элементүүдийн тоо юм. Үүсгэсэн хэш багцад хамгийн ихдээ n элемент байж болох тул орон зайн нарийн төвөгтэй байдал нь шугаман байна.