Ёфтан мумкин аст, ки агар 0 зергурӯҳ бо XNUMX сум бошад  


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Citrix DE Шо Голдман Sachs Ҳақиқатан MakeMyTrip Хонаҳои OYO Пардохт TCS
тартиботи ҳарбӣ Хаш

Масъалаи "Ёбед, агар зергурӯҳ бо 0 сум бошад" гуфта шудааст, ки ба шумо ан ҳамаҷониба асал дорои ададҳои манфӣ низ мебошанд. Дар изҳороти масъала муайян карда мешавад, ки оё ягон зеркатри андозаи ҳадди аққал 1 муайян карда мешавад, ки ин зерматрис бояд маблағи ба 1 баробар дошта бошад.

мисол  

Ёфтан мумкин аст, ки агар 0 зергурӯҳ бо XNUMX сум бошад

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

Шарҳ

Дар ин ҷо, унсурҳои аз индекси 0 то 2 маблағи 0 доранд.

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

Шарҳ

Ягон зеркатри вуҷуд надорад, ки маблағи 0 дошта бошад.

Алгоритм  

  1. Эълом кунед a маҷмӯи.
  2. Оғоз маҷмӯа ба 0.
  3. Дар ҳоле, ки массивро тай кунед i <n (дарозии массив).
    1. Сумро ба arr [i] илова кунед ва онро ба сум нигоҳ доред.
    2. Дуруст будани ягон шартҳои зеринро санҷед:
      1. sum == 0 / arr [i] == 0 / if Set арзиши суммаро дар бар гирад.
      2. агар рост бошад, пас ҳақро баргардонед.
    3. Маблағро ба Маҷмӯа илова кунед.
  4. Бозгаштан бардурӯғ.

Шарҳ

Мо як изҳороти проблемавӣ гирифтем, ки хоҳем фаҳмид, ки ягон зерсатр мавҷуд аст, ки маблағи он ба 0 баробар аст. Барои ҳалли ин масъала мо маҷмӯаро барои ҳалли ин масъала истифода хоҳем кард. Мо унсурҳои массиви додашударо дар маҷмӯа нигоҳ медорем. Он гоҳ ҳамзамон қиматро ба сумма илова кунед ва санҷед, ки оё ягон мувофиқати суб-массив бо суммаи ҳозира дар маҷмӯъ мавҷуд аст ё худи ҷамъ ба 0 баробар аст. дуруст.

Агар ҳеҷ кадоме аз зеркатроҳо суммаи 0 надошта бошанд, пас мо аз ҳалқа баргаштанро бармегардонем. Инчунин, як чиз ҳаст, агар ягон элемент 0 бошад, пас мо ҳақиқиро бармегардем, зеро унсур худ зеркатри як унсури ягона мебошад. Ҳамин тавр, ин маънои онро дорад, ки мо яке аз чунин зергурӯҳҳоро ёфтем.

ҳамчунин нигаред
Ададҳое, ки басомади аввалашон аз k калон ё ба он баробаранд

Дар ин ҷо, мо функсияи Boolean -ро эълон менамоем, он ё true ё false бармегардад, агар зеркатри массив ёфт шавад, true бармегардад, вагарна бардурӯғ бармегардад.

Биёед як мисолро дида бароем:

мисол

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

Дар ин ҷо, дар код, мо массивро тай карда, сумма ва arr [i] -ро илова мекунем ва ба сумма нигоҳ медорем ва пас аз тафтиш, агар sum == 0 ё arr [i] ба 0 баробар бошад ё Set арзиши суммаро дар бар гирад, Агар ягон шарти додашуда қонеъ карда шавад, пас мо ҳақиқиро бармегардонем ва сипас ба Set маблағ илова мекунем.

Агар ҳеҷ кадоме аз зеркатраса пайдо нашавад, пас мо бармегардем.

сумма = 0, Танзими = {}

i = 0, arr [i] = -3

сумма = сумма + arr [i] => 0 + - 3 = -3

агар sum == 0 ё arr [i] ба 0 баробар бошад ё Set арзиши суммаро дар бар гирад, сеяки онҳо нодуруст аст, бинобар ин мо ҳеҷ коре намекунем ва ба Set -3 илова мекунем.

i = 1, arr [i] = 2

сумма = сумма + arr [i] => -3 + 2 = -1

агар sum == 0 ё arr [i] ба 0 баробар бошад ё Set арзиши суммаро дар бар гирад, сеяки онҳо нодуруст аст, бинобар ин мо ҳеҷ коре намекунем ва ба Set -1 илова мекунем.

i = 2, arr [i] = 1

сумма = сумма + arr [i] => -1 + 1 = 0

агар маблағи == 0 дар инҷо қонеъ карда шавад, пас мо ҳақиқӣ бармегардем, ин маънои зерқаторро бо суммаи 0 пайдо кардем.

Натиҷа: Бале, зеркатраса бо суммаи 0 вуҷуд дорад.

рамз  

Коди C ++ барои дарёфт кардани он, ки subarray бо 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

Таҳлили мураккабӣ  

Мураккабии вақт

Эй (н) ки дар "Н" шумораи унсурҳои массив аст. Ҳамаи ин ба туфайли истифодаи HashSet имконпазир буд, зеро он ба мо имкон медиҳад, ки дар вақти O (1) дохилкунӣ, ҷустуҷӯ ва несткуниро иҷро кунем.

ҳамчунин нигаред
Вақти беҳтарин барои харидан ва фурӯхтан Stock II Leetcode Solution

Мураккабии фазо

Эй (н) ки дар "Н" шумораи унсурҳои массив аст. Азбаски дар маҷмӯи хэши эҷодшуда ҳадди аксар n элемент мавҷуд буда метавонад, мураккабии фазо хаттӣ аст.