Dado un arreglo arr[] de tamaño N , la tarea es encontrar el número de subarreglos que tienen una suma de sus elementos igual al número de elementos en él.
Ejemplos:
Entrada : N = 3, arr[] = {1, 0, 2}
Salida: 3
Explicación:
el número total de subarreglos es 6, es decir, {1}, {0}, {2}, {1, 0}, {0 , 2}, {1, 0, 2}.
De los 6 subarreglos, los tres siguientes satisfacen las condiciones dadas:
- {1}: Suma = 1, Longitud = 1
- {0, 2}: Suma = 2, Longitud = 2
- {1, 0, 2}: Suma = 3, Longitud = 3
Entrada: N = 3, arr[] = {1, 1, 0}
Salida: 3
Explicación:
El número total de subarreglos es 6, es decir, {1}, {1}, {0}, {1, 1}, {1 , 0}, {1, 1, 0}.
De los 6 subarreglos, los tres siguientes satisfacen las condiciones dadas:
- {1}: Suma = 1, Longitud = 1
- {1, 1}: Suma = 2, Longitud = 2
- {1}: Suma = 1, Longitud = 1
Entrada: N = 6, arr[] = {1, 1, 1} Salida: 3 Explicación: el número total de subarreglos es 6, es decir, {1}, {1}, {1}, {1, 1}, {1, 1}, {1, 1, 1}. De los 6 subarreglos, los siguientes seis subarreglos satisfacen las condiciones dadas:
- {1},{1},{1}: Suma=1, Longitud=1, Número de subarreglos=3
- {1,1},{1,1}: Suma=2, Longitud=2, Número de subarreglos=2
- {1,1,1}: Suma=3, Longitud=3, Número de subarreglos=1
Número total de subarreglos que tienen Suma igual a su Longitud = 6
Enfoque ingenuo y basado en la suma de prefijos : consulte la publicación anterior para conocer los enfoques más simples y basados en la suma de prefijos para resolver el problema.
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es almacenar las ocurrencias anteriores de subarreglos con las condiciones dadas y hacer uso de unordered_map para una búsqueda constante. A continuación se muestran los pasos:
- Inicialice un mapa unordered_map M , responda para almacenar el recuento de subarreglos y sum para almacenar el prefijo sum del arreglo .
- Recorre la array dada y haz lo siguiente:
- Agregue el elemento actual a la suma .
- Si M[sum – i] existe, agregue este valor a la respuesta ya que existe un subarreglo de longitud i cuya suma del elemento es la suma actual .
- Incrementa la frecuencia de (suma – i) en el mapa M .
- Después de los pasos anteriores, imprima el valor de la respuesta como el recuento total de subarreglos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function that counts the subarrays
// with sum of its elements as its length
int countOfSubarray(int arr[], int N)
{
// Store count of elements upto
// current element with length i
unordered_map<int, int> mp;
// Stores the final count of subarray
int answer = 0;
// Stores the prefix sum
int sum = 0;
// If size of subarray is 1
mp[1]++;
// Iterate the array
for (int i = 0; i < N; i++) {
// Find the sum
sum += arr[i];
answer += mp[sum - i];
// Update frequency in map
mp[sum - i]++;
}
// Print the total count
cout << answer;
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 1, 0, 2, 1, 2, -2, 2, 4 };
// Size of array
int N = sizeof arr / sizeof arr[0];
// Function Call
countOfSubarray(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function that counts the subarrays
// with sum of its elements as its length
static void countOfSubarray(int arr[], int N)
{
// Store count of elements upto
// current element with length i
Map<Integer,
Integer> mp = new HashMap<Integer,
Integer>();
// Stores the final count of subarray
int answer = 0;
// Stores the prefix sum
int sum = 0;
// If size of subarray is 1
if (mp.get(1) != null)
mp.put(1, mp.get(1) + 1);
else
mp.put(1, 1);
// Iterate the array
for(int i = 0; i < N; i++)
{
// Find the sum
sum += arr[i];
if (mp.get(sum - i) != null)
answer += mp.get(sum - i);
// Update frequency in map
if (mp.get(sum - i) != null)
mp.put(sum - i, mp.get(sum - i) + 1);
else
mp.put(sum - i, 1);
}
// Print the total count
System.out.print(answer);
}
// Driver Code
public static void main(String args[])
{
// Given array arr[]
int arr[] = { 1, 0, 2, 1, 2, -2, 2, 4 };
// Size of array
int N = arr.length;
// Function Call
countOfSubarray(arr, N);
}
}
// This code is contributed by ipg2016107
Python3
# Python3 program for the above approach from collections import defaultdict # Function that counts the subarrays # with sum of its elements as its length def countOfSubarray(arr, N): # Store count of elements upto # current element with length i mp = defaultdict(lambda : 0) # Stores the final count of subarray answer = 0 # Stores the prefix sum sum = 0 # If size of subarray is 1 mp[1] += 1 # Iterate the array for i in range(N): # Find the sum sum += arr[i] answer += mp[sum - i] # Update frequency in map mp[sum - i] += 1 # Print the total count print(answer) # Driver code if __name__ == '__main__': # Given array arr = [ 1, 0, 2, 1, 2, -2, 2, 4 ] # Size of the array N = len(arr) # Function Call countOfSubarray(arr, N) # This code is contributed by Shivam Singh
C#
// C# program for the
// above approach
using System;
using System.Collections.Generic;
class GFG{
// Function that counts
// the subarrays with sum
// of its elements as its length
static void countOfSubarray(int []arr,
int N)
{
// Store count of elements upto
// current element with length i
Dictionary<int,
int> mp = new Dictionary<int,
int>();
// Stores the readonly
// count of subarray
int answer = 0;
// Stores the prefix sum
int sum = 0;
// If size of subarray is 1
mp[1] = 1;
// Iterate the array
for(int i = 0; i < N; i++)
{
// Find the sum
sum += arr[i];
if (mp.ContainsKey(sum - i))
answer += mp[sum - i];
// Update frequency in map
if(mp.ContainsKey(sum - 1))
mp[sum - 1]++;
else
mp[sum - 1] = 1;
}
// Print the total count
Console.Write(answer - 2);
}
// Driver Code
public static void Main(String []args)
{
// Given array []arr
int []arr = {1, 0, 2, 1,
2, -2, 2, 4};
// Size of array
int N = arr.Length;
// Function Call
countOfSubarray(arr, N);
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// JavaScript program for the above approach
// Function that counts the subarrays
// with sum of its elements as its length
function countOfSubarray(arr, N)
{
// Store count of elements upto
// current element with length i
var mp = new Map();
// Stores the final count of subarray
var answer = 0;
// Stores the prefix sum
var sum = 0;
// If size of subarray is 1
if(!mp.has(1))
mp.set(1, 1)
else
mp.set(1, mp.get(1)+1)
// Iterate the array
for (var i = 0; i < N; i++) {
// Find the sum
sum += arr[i];
answer += mp.has(sum - i)?mp.get(sum - i):0;
// Update frequency in map
if(mp.has(sum - i))
mp.set(sum - i, mp.get(sum - i)+1)
else
mp.set(sum - i, 1)
}
// Print the total count
document.write( answer);
}
// Driver Code
// Given array arr[]
var arr = [1, 0, 2, 1, 2, -2, 2, 4];
// Size of array
var N = arr.length;
// Function Call
countOfSubarray(arr, N);
</script>
7
Complejidad temporal: O(N)
Espacio auxiliar: O(N)