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

01.01.2020Хеш

Учитывая массив положительных и отрицательных чисел, найдите, есть ли подмассив (размером не менее одного) с 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 ² ).

Мы также можем использовать хеширование . Идея состоит в том, чтобы перебрать массив и для каждого элемента 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