Dada una array arr[] de tamaño N, la tarea es contar el número total de subarreglos para la array dada arr[] que tienen una suma distinta de cero.
Ejemplos:
Entrada: arr[] = {-2, 2, -3}
Salida: 4
Explicación:
Los subarreglos con suma distinta de cero son: [-2], [2], [2, -3], [-3]. Todos los subarreglos posibles de la array de entrada dada son [-2], [2], [-3], [2, -2], [2, -3], [-2, 2, -3]. De estos [2, -2] no se incluye en el conteo porque 2+(-2) = 0 y [-2, 2, -3] no se selecciona porque uno de los subarreglo [2, -2] de este arreglo tiene una suma cero de elementos.
Entrada: array[] = {1, 3, -2, 4, -1}
Salida: 15
Explicación:
Hay 15 subarreglos para la array dada {1, 3, -2, 4, -1} que tiene un valor distinto de cero suma.
Enfoque:
La idea principal para resolver la pregunta anterior es usar Prefix Sum Array y Map Data Structure .
- Primero, construya la array de suma de prefijos de la array dada y use la fórmula a continuación para verificar si la subarreglo tiene una suma de elementos de 0.
Suma de subarreglo[L, R] = Prefijo[R] – Prefijo[L – 1]. Entonces, si la suma de subarreglo [L, R] = 0
, entonces, Prefijo [R] – Prefijo [L – 1] = 0. Por lo tanto, Prefijo [R] = Prefijo [L – 1]
- Ahora, itere de 1 a N y mantenga una tabla Hash para almacenar el índice de la aparición anterior del elemento y una variable, digamos last , e inicialícelo en 0.
- Compruebe si Prefix[i] ya está presente en el Hash o no. En caso afirmativo, actualice last as last = max(last, hash[Prefix[i]] + 1) . De lo contrario, agregue i – last a la respuesta y actualice la tabla Hash.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to Count the total number of
// subarrays for a given array such that its
// subarray should have non zero sum
#include <bits/stdc++.h>
using namespace std;
// Function to build the Prefix sum array
vector<int> PrefixSumArray(int arr[], int n)
{
vector<int> prefix(n);
// Store prefix of the first position
prefix[0] = arr[0];
for (int i = 1; i < n; i++)
prefix[i] = prefix[i - 1] + arr[i];
return prefix;
}
// Function to return the Count of
// the total number of subarrays
int CountSubarray(int arr[], int n)
{
vector<int> Prefix(n);
// Calculating the prefix array
Prefix = PrefixSumArray(arr, n);
int last = 0, ans = 0;
map<int, int> Hash;
Hash[0] = -1;
for (int i = 0; i <= n; i++) {
// Check if the element already exists
if (Hash.count(Prefix[i]))
last = max(last, Hash[Prefix[i]] + 1);
ans += max(0, i - last);
// Mark the element
Hash[Prefix[i]] = i;
}
// Return the final answer
return ans;
}
// Driver code
int main()
{
int arr[] = { 1, 3, -2, 4, -1 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << CountSubarray(arr, N);
}
Java
// Java program to count the total number of
// subarrays for a given array such that its
// subarray should have non zero sum
import java.util.*;
class GFG{
// Function to build the Prefix sum array
static int[] PrefixSumArray(int arr[], int n)
{
int []prefix = new int[n];
// Store prefix of the first position
prefix[0] = arr[0];
for(int i = 1; i < n; i++)
prefix[i] = prefix[i - 1] + arr[i];
return prefix;
}
// Function to return the Count of
// the total number of subarrays
static int CountSubarray(int arr[], int n)
{
int []Prefix = new int[n];
// Calculating the prefix array
Prefix = PrefixSumArray(arr, n);
int last = 0, ans = 0;
HashMap<Integer,
Integer> Hash = new HashMap<Integer,
Integer>();
Hash.put(0, -1);
for(int i = 0; i <= n; i++)
{
// Check if the element already exists
if (i < n && Hash.containsKey(Prefix[i]))
last = Math.max(last,
Hash.get(Prefix[i]) + 1);
ans += Math.max(0, i - last);
// Mark the element
if (i < n)
Hash.put(Prefix[i], i);
}
// Return the final answer
return ans;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 3, -2, 4, -1 };
int N = arr.length;
System.out.print(CountSubarray(arr, N));
}
}
// This code is contributed by amal kumar choubey
Python3
# Python3 program to count the total number
# of subarrays for a given array such that
# its subarray should have non zero sum
# Function to build the prefix sum array
def PrefixSumArray(arr, n):
prefix = [0] * (n + 1);
# Store prefix of the first position
prefix[0] = arr[0];
for i in range(1, n):
prefix[i] = prefix[i - 1] + arr[i];
return prefix;
# Function to return the count of
# the total number of subarrays
def CountSubarray(arr, n):
Prefix = [0] * (n + 1);
# Calculating the prefix array
Prefix = PrefixSumArray(arr, n);
last = 0; ans = 0;
Hash = {};
Hash[0] = -1;
for i in range(n + 1):
# Check if the element already exists
if (Prefix[i] in Hash):
last = max(last, Hash[Prefix[i]] + 1);
ans += max(0, i - last);
# Mark the element
Hash[Prefix[i]] = i;
# Return the final answer
return ans;
# Driver code
if __name__ == "__main__" :
arr = [ 1, 3, -2, 4, -1 ];
N = len(arr);
print(CountSubarray(arr, N));
# This code is contributed by AnkitRai01
C#
// C# program to count the total number of
// subarrays for a given array such that its
// subarray should have non zero sum
using System;
using System.Collections.Generic;
class GFG{
// Function to build the Prefix sum array
static int[] PrefixSumArray(int []arr, int n)
{
int []prefix = new int[n];
// Store prefix of the first position
prefix[0] = arr[0];
for(int i = 1; i < n; i++)
prefix[i] = prefix[i - 1] + arr[i];
return prefix;
}
// Function to return the Count of
// the total number of subarrays
static int CountSubarray(int []arr, int n)
{
int []Prefix = new int[n];
// Calculating the prefix array
Prefix = PrefixSumArray(arr, n);
int last = 0, ans = 0;
Dictionary<int,
int> Hash = new Dictionary<int,
int>();
Hash.Add(0, -1);
for(int i = 0; i <= n; i++)
{
// Check if the element already exists
if (i < n && Hash.ContainsKey(Prefix[i]))
last = Math.Max(last,
Hash[Prefix[i]] + 1);
ans += Math.Max(0, i - last);
// Mark the element
if (i < n)
Hash.Add(Prefix[i], i);
}
// Return the readonly answer
return ans;
}
// Driver code
public static void Main(String[] args)
{
int []arr = {1, 3, -2, 4, -1};
int N = arr.Length;
Console.Write(CountSubarray(arr, N));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program to count the total number of
// subarrays for a given array such that its
// subarray should have non zero sum
// Function to build the Prefix sum array
function PrefixSumArray(arr, n)
{
let prefix = Array.from({length: n}, (_, i) => 0);
// Store prefix of the first position
prefix[0] = arr[0];
for(let i = 1; i < n; i++)
prefix[i] = prefix[i - 1] + arr[i];
return prefix;
}
// Function to return the Count of
// the total number of subarrays
function CountSubarray(arr, n)
{
let Prefix = Array.from({length: n}, (_, i) => 0);
// Calculating the prefix array
Prefix = PrefixSumArray(arr, n);
let last = 0, ans = 0;
let Hash = new Map();
Hash.set(0, -1);
for(let i = 0; i <= n; i++)
{
// Check if the element already exists
if (i < n && Hash.has(Prefix[i]))
last = Math.max(last,
Hash.get(Prefix[i]) + 1);
ans += Math.max(0, i - last);
// Mark the element
if (i < n)
Hash.set(Prefix[i], i);
}
// Return the final answer
return ans;
}
// Driver code
let arr = [ 1, 3, -2, 4, -1 ];
let N = arr.length;
document.write(CountSubarray(arr, N));
// This code is contributed by code_hunt.
</script>
Producción:
15
Complejidad temporal: O(N)
Espacio auxiliar: O(N)