Рубрики

Найти, есть ли подмассив с 0 суммой

Учитывая массив положительных и отрицательных чисел, найдите, есть ли подмассив (размером не менее одного) с 0 суммой.

Примеры :

Input: {4, 2, -3, 1, 6}
Output: true 
There is a subarray with zero sum from index 1 to 3.

Input: {4, 2, 0, 1, 6}
Output: true 
There is a subarray with zero sum from index 2 to 2.

Input: {-3, 2, 3, 1, 6}
Output: false
There is no subarray with zero sum.

Простое решение состоит в том, чтобы рассмотреть все подмассивы один за другим и проверить сумму каждого подмассива. Мы можем запустить два цикла: внешний цикл выбирает начальную точку i, а внутренний цикл пробует все подмассивы, начиная с i (см. Это для реализации). Временная сложность этого метода составляет O (n 2 ).

Мы также можем использовать хеширование . Идея состоит в том, чтобы перебрать массив и для каждого элемента arr [i] вычислить сумму элементов от 0 до i (это можно сделать просто как sum + = arr [i]). Если текущая сумма была замечена ранее, то существует массив с нулевой суммой. Хеширование используется для хранения значений суммы, чтобы мы могли быстро сохранить сумму и выяснить, видна ли текущая сумма раньше или нет.

Пример :

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

If we consider all prefix sums, we can
notice that there is a subarray with 0
sum when :
1) Either a prefix sum repeats or
2) Or prefix sum becomes 0.

Prefix sums for above array are:
1, 5, 3, 1, 6, 2, 5

Since prefix sum 1 repeats, we have a subarray
with 0 sum. 

Ниже приводится реализация вышеуказанного подхода.

C ++

// Программа на C ++ для поиска нулевой суммы
// подрешетка
#include <bits/stdc++.h>

using namespace std;

  

bool subArrayExists(int arr[], int n)

{

    unordered_set<int> sumSet;

  

    // Обход массива и сохранение сумм префиксов

    int sum = 0;

    for (int i = 0 ; i < n ; i++)

    {

        sum += arr[i];

  

        // Если сумма префикса равна 0 или она уже присутствует

        if (sum == 0 || sumSet.find(sum) != sumSet.end())

            return true;

  

        sumSet.insert(sum);

    }

    return false;

}

  
// Код драйвера

int main()

{

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

    int n = sizeof(arr)/sizeof(arr[0]);

    if (subArrayExists(arr, n))

        cout << "Found a subarray with 0 sum";

    else

        cout << "No Such Sub Array Exists!";

    return 0;

}

Джава

// Java-программа для поиска подмассива с нулевой суммой

import java.util.HashMap;

  

class ZeroSumSubarray {

      

    // Возвращает true, если arr [] имеет подмассив с серой суммой

    static Boolean subArrayExists(int arr[])

    {

        // Создает пустой hashMap hM

        HashMap<Integer, Integer> hM = 

                        new HashMap<Integer, Integer>();

          

        // Инициализируем сумму элементов

        int sum = 0;     

          

        // Пройти через данный массив

        for (int i = 0; i < arr.length; i++)

        

            // Добавить текущий элемент в сумму

            sum += arr[i];

              

            // Возвращаем true в следующих случаях

            // а) Текущий элемент равен 0

            // б) сумма элементов от 0 до i равна 0

            // c) сумма уже присутствует в хэш-карте

            if (arr[i] == 0 || sum == 0 || hM.get(sum) != null)                         

                return true;

              

            // Добавить сумму к хэш-карте

            hM.put(sum, i);

        

          

        // Мы достигаем здесь только тогда, когда есть

        // нет подмассива с 0 суммой

        return false;

    }     

      

    // код драйвера

    public static void main(String arg[])

    {

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

        if (subArrayExists(arr))

            System.out.println("Found a subarray with 0 sum");

        else

            System.out.println("No Such Sub Array Exists!");         

    }         

}

python3

# Программа Python, чтобы найти, если
# есть подмассив с нулевой суммой

  

def subArrayExists(arr,n):

    s = set()

  

    # пройти через массив

    # и хранить префиксные суммы

    sum = 0

    for i in range(n):

        sum += arr[i]

  

        # Если сумма префикса равна 0 или

        # оно уже присутствует

        if sum == 0 or sum in s:

            return True

        s.add(sum)

          

    return False

  
# Код драйвера

arr = [-3, 2, 3, 1, 6]

n = len(arr)

if subArrayExists(arr, n) == True:

    print("Found a sunbarray with 0 sum")

else:

    print("No Such sub array exits!")

  
# Этот код предоставлен Shrikant13

C #

// AC # программа, чтобы найти, если есть
// подмассив с нулевой суммой

using System;

using System.Collections.Generic;

  

class GFG

{
// Возвращает true, если arr [] имеет
// подрешетка с серосуммой

    static Boolean subArrayExists(int []arr)

    {

        // Создает пустой hashMap hM

        Dictionary<int

                   int> hM = new Dictionary<int

                                            int>();

        // Инициализируем сумму элементов

        int sum = 0;     

          

        // Пройти через данный массив

        for (int i = 0; i < arr.Length; i++)

        

            // Добавить текущий элемент в сумму

            sum += arr[i];

              

            // Возвращаем true в следующих случаях

            // а) Текущий элемент равен 0

            // б) сумма элементов от 0 до i равна 0

            // c) сумма уже присутствует в хэш-карте

            if (arr[i] == 0 || sum == 0 )                         

                return true;

              

            // Добавить сумму к хэш-карте

            hM[i] = sum;

        

          

        // Мы достигаем здесь только тогда, когда есть

        // нет подмассива с 0 суммой

        return false;

    }     

      

    // Код драйвера

    public static void Main()

    {

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

        if (subArrayExists(arr))

            Console.WriteLine("Found a subarray "

                                     "with 0 sum");

        else

            Console.WriteLine("No Such Sub "

                             "Array Exists!"); 

    }

}

  
// Этот код предоставлен Sam007


Выход :

No Such Sub Array Exists!

Сложность по времени этого решения можно рассматривать как O (n) в предположении, что у нас есть хорошая функция хеширования, которая позволяет операции вставки и извлечения за время O (1).

Упражнение:
Расширьте вышеприведенную программу для печати начальных и конечных индексов всех подмассивов с 0 суммой.

Эта статья предоставлена Чираг Гупта . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Найти, есть ли подмассив с 0 суммой

0.00 (0%) 0 votes