Рубрики

Найти длину наибольшего подмассива с 0 суммой

По массиву целых чисел найдите длину самого длинного подмассива с суммой, равной 0.

Примеры :

Input: arr[] = {15, -2, 2, -8, 1, 7, 10, 23};
Output: 5
The largest subarray with 0 sum is -2, 2, -8, 1, 7

Input: arr[] = {1, 2, 3}
Output: 0
There is no subarray with 0 sum

Input: arr[] = {1, 0, 3}
Output: 1

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

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

C / C ++

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

using namespace std;

  
// Возвращает длину наибольшего подмассива с 0 суммой

int maxLen(int arr[], int n)

{

    int max_len = 0; // Инициализировать результат

  

    // Выберите начальную точку

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

        // Инициализируем currr_sum для каждой начальной точки

        int curr_sum = 0;

  

        // пробуем все подмассивы, начинающиеся с 'i'

        for (int j = i; j < n; j++) {

            curr_sum += arr[j];

  

            // Если curr_sum становится 0, тогда обновляем max_len

            // если необходимо

            if (curr_sum == 0)

                max_len = max(max_len, j - i + 1);

        }

    }

    return max_len;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int arr[] = { 15, -2, 2, -8, 1, 7, 10, 23 };

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

    cout << "Length of the longest 0 sum subarray is "

         << maxLen(arr, n);

    return 0;

}

Джава

// Java-код для поиска наибольшего подмассива
// с 0 суммой

class GFG {

    // Возвращает длину наибольшего подмассива

    // с 0 суммой

    static int maxLen(int arr[], int n)

    {

        int max_len = 0;

  

        // Выберите начальную точку

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

            // Инициализируем curr_sum для каждого

            // отправная точка

            int curr_sum = 0;

  

            // пробуем все подмассивы, начинающиеся с 'i'

            for (int j = i; j < n; j++) {

                curr_sum += arr[j];

  

                // Если curr_sum становится 0, тогда обновляем

                // max_len

                if (curr_sum == 0)

                    max_len = Math.max(max_len, j - i + 1);

            }

        }

        return max_len;

    }

  

    public static void main(String args[])

    {

        int arr[] = { 15, -2, 2, -8, 1, 7, 10, 23 };

        int n = arr.length;

        System.out.println("Length of the longest 0 sum "

                           + "subarray is " + maxLen(arr, n));

    }

}
// Этот код предоставлен Камалем Равалом

питон

# Программа Python для определения длины наибольшего подмассива с 0 суммой

  
# возвращает длину

def maxLen(arr):

      

    # инициализировать результат

    max_len = 0

  

    # выбрать отправную точку

    for i in range(len(arr)):

          

        # инициализировать сумму для каждой начальной точки

        curr_sum = 0

          

        # попробуйте все подмассивы, начинающиеся с 'i'

        for j in range(i, len(arr)):

          

            curr_sum += arr[j]

  

            # если curr_sum становится 0, тогда обновите max_len

            if curr_sum == 0:

                max_len = max(max_len, j-i + 1)

  

    return max_len

  

  
# тестовый массив

arr = [15, -2, 2, -8, 1, 7, 10, 13]

  

print "Length of the longest 0 sum subarray is % d" % maxLen(arr) 

C #

// C # код, чтобы найти самый большой
// подрешетка с 0 суммой

using System;

  

class GFG {

    // Возвращает длину

    // самый большой подмассив с 0 суммой

    static int maxLen(int[] arr, int n)

    {

        int max_len = 0;

  

        // Выберите начальную точку

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

            // Инициализация curr_sum

            // для каждой начальной точки

            int curr_sum = 0;

  

            // попробовать все подмассивы

            // начинаем с 'i'

            for (int j = i; j < n; j++) {

                curr_sum += arr[j];

  

                // Если curr_sum становится 0,

                // затем обновляем max_len

                if (curr_sum == 0)

                    max_len = Math.Max(max_len,

                                       j - i + 1);

            }

        }

        return max_len;

    }

  

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

    static public void Main()

    {

        int[] arr = { 15, -2, 2, -8,

                      1, 7, 10, 23 };

        int n = arr.Length;

        Console.WriteLine("Length of the longest 0 sum "

                          + "subarray is " + maxLen(arr, n));

    }

}

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

PHP

<?php
// Простая PHP-программа для поиска
// самый большой подмассив с 0 суммой

  
// Возвращает длину
// самый большой подмассив с 0 суммой

function maxLen($arr, $n)

{

    $max_len = 0; // Инициализировать результат

  

    // Выберите начальную точку

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

    {

        // Инициализация currr_sum

        // для каждой начальной точки

        $curr_sum = 0;

  

        // попробовать все подмассивы

        // начинаем с 'i'

        for ($j = $i; $j < $n; $j++)

        {

            $curr_sum += $arr[$j];

  

            // Если curr_sum становится 0,

            // затем обновляем max_len

            // если необходимо

            if ($curr_sum == 0)

            $max_len = max($max_len

                           $j - $i + 1);

        }

    }

    return $max_len;

}

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

$arr = array(15, -2, 2, -8,

              1, 7, 10, 23);

$n = sizeof($arr);

echo "Length of the longest 0 "

              "sum subarray is ",

                maxLen($arr, $n);

      
// Этот код предоставлен aj_36
?>


Выход :

Length of the longest 0 sum subarray is 5

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

Ниже приведен пробный запуск вышеуказанного подхода:

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

C ++

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

using namespace std;

  
// Возвращает длину требуемого подмассива

int maxLen(int arr[], int n)

{

    // Карта для хранения предыдущих сумм

    unordered_map<int, int> presum;

  

    int sum = 0; // Инициализируем сумму элементов

    int max_len = 0; // Инициализировать результат

  

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

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

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

        sum += arr[i];

  

        if (arr[i] == 0 && max_len == 0)

            max_len = 1;

        if (sum == 0)

            max_len = i + 1;

  

        // Ищите эту сумму в хэш-таблице

        if (presum.find(sum) != presum.end()) {

            // Если эта сумма видна раньше, то обновляем max_len

            max_len = max(max_len, i - presum[sum]);

        }

        else {

            // Иначе вставляем эту сумму с индексом в хеш-таблицу

            presum[sum] = i;

        }

    }

  

    return max_len;

}

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

int main()

{

    int arr[] = { 15, -2, 2, -8, 1, 7, 10, 23 };

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

    cout << "Length of the longest 0 sum subarray is "

         << maxLen(arr, n);

  

    return 0;

}

Джава

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

import java.util.HashMap;

  

class MaxLenZeroSumSub {

  

    // Возвращает длину подмассива максимальной длины с 0 суммой

    static int maxLen(int arr[])

    {

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

        HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>();

  

        int sum = 0; // Инициализируем сумму элементов

        int max_len = 0; // Инициализировать результат

  

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

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

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

            sum += arr[i];

  

            if (arr[i] == 0 && max_len == 0)

                max_len = 1;

  

            if (sum == 0)

                max_len = i + 1;

  

            // Посмотрим эту сумму в хеш-таблице

            Integer prev_i = hM.get(sum);

  

            // Если эта сумма видна раньше, то обновляем max_len

            // если необходимо

            if (prev_i != null)

                max_len = Math.max(max_len, i - prev_i);

            else // Иначе положить эту сумму в хеш-таблицу

                hM.put(sum, i);

        }

  

        return max_len;

    }

  

    // Метод привода

    public static void main(String arg[])

    {

        int arr[] = { 15, -2, 2, -8, 1, 7, 10, 23 };

        System.out.println("Length of the longest 0 sum subarray is "

                           + maxLen(arr));

    }

}

питон

# Программа на Python для поиска подмассива максимальной длины
# с 0 суммой за o (n) время

  
# Возвращает максимальную длину

def maxLen(arr):

      

    # ПРИМЕЧАНИЕ: Dictonary в python реализован как Hash Maps

    # Создать пустую хеш-карту (словарь)

    hash_map = {}

  

    # Инициализировать результат

    max_len = 0

  

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

    curr_sum = 0

  

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

    for i in range(len(arr)):

          

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

        curr_sum += arr[i]

  

        if arr[i] is 0 and max_len is 0:

            max_len = 1

  

        if curr_sum is 0:

            max_len = i + 1

  

        # ПРИМЕЧАНИЕ: операция «в» в словаре для поиска

        Клавиша # занимает O (1). Посмотрите, видна ли текущая сумма

        # перед

        if curr_sum in hash_map:

            max_len = max(max_len, i - hash_map[curr_sum] )

        else:

  

            # еще положить эту сумму в словарь

            hash_map[curr_sum] = i

  

    return max_len

  

  
# тестовый массив

arr = [15, -2, 2, -8, 1, 7, 10, 13]

   

print "Length of the longest 0 sum subarray is % d" % maxLen(arr)

C #

// C # программа для поиска максимума
// длина подмассива с 0 суммой

using System;

using System.Collections.Generic;

  

public class MaxLenZeroSumSub {

  

    // Возвращает длину максимума

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

    static int maxLen(int[] arr)

    {

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

        Dictionary<int, int> hM = new Dictionary<int, int>();

  

        int sum = 0; // Инициализируем сумму элементов

        int max_len = 0; // Инициализировать результат

  

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

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

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

            sum += arr[i];

  

            if (arr[i] == 0 && max_len == 0)

                max_len = 1;

  

            if (sum == 0)

                max_len = i + 1;

  

            // Посмотрим эту сумму в хеш-таблице

            int prev_i = 0;

            if (hM.ContainsKey(sum)) {

                prev_i = hM[sum];

            }

  

            // Если эта сумма видна раньше, то обновляем max_len

            // если необходимо

            if (hM.ContainsKey(sum))

                max_len = Math.Max(max_len, i - prev_i);

            else {

                // Иначе положить эту сумму в хеш-таблицу

                if (hM.ContainsKey(sum))

                    hM.Remove(sum);

  

                hM.Add(sum, i);

            }

        }

  

        return max_len;

    }

  

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

    public static void Main()

    {

        int[] arr = { 15, -2, 2, -8, 1, 7, 10, 23 };

        Console.WriteLine("Length of the longest 0 sum subarray is "

                          + maxLen(arr));

    }

}

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

Выход :

Length of the longest 0 sum subarray is 5

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

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

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

Найти длину наибольшего подмассива с 0 суммой

0.00 (0%) 0 votes