Recuento de subarreglos que tienen una suma igual a su longitud – Part 1

Dado un arreglo arr[] de tamaño N , la tarea es encontrar el número de subarreglos que tienen la 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 6, solo tres subarreglos tienen el número de elementos igual a la suma de sus elementos, es decir, 
1) {1}, sum = 1, length = 1.
2) {0, 2}, sum = 2, length = 2.
3 ) {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 6, solo tres subarreglos tienen el número de elementos igual a la suma de sus elementos, es decir, 
1) {1}, sum = 1, length = 1.
2) {1}, sum = 1, length = 1.
3) { 1, 1}, suma = 2, longitud = 2.

Enfoque ingenuo: la idea es generar todos los subarreglos del arreglo y si la suma de los elementos del subarreglo es igual al número de elementos que contiene, entonces cuente este subarreglo. Imprima el conteo después de verificar todos los subarreglos.

Tiempo Complejidad: O(N ² )
Espacio Auxiliar: O(N)

Enfoque eficiente: este problema se puede convertir en un problema más simple mediante el uso de la observación. Si todos los elementos del arreglo se reducen en 1 , entonces todos los subarreglos del arreglo arr[] con una suma igual a su número de elementos son lo mismo que encontrar el número de subarreglos con suma 0 en el nuevo arreglo (formado al decrementar todos los elementos de arr[ ] por 1). A continuación se muestran los pasos:

1. Decrementa todos los elementos de la array en 1.
2. Inicialice una array de prefijos con prefix[0] = arr[0] .
3. Recorra la array dada arr[] de izquierda a derecha, comenzando desde el índice 1 y actualice una array de suma de prefijos como pref[i] = pref[i-1] + arr[i] .
4. Inicializar la respuesta a 0.
5. Repita la array de prefijos pref[] de izquierda a derecha e incremente la respuesta por el valor del elemento actual en el mapa .
6. Incrementa el valor del elemento actual en el mapa.
7. Imprime el valor de la respuesta después de los pasos anteriores.

A continuación se muestra la implementación del enfoque anterior:

// 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)
{
    // Decrementing all the elements
    // of the array by 1
    for (int i = 0; i < N; i++)
        arr[i]--;
 
    // Making prefix sum array
    int pref[N];
    pref[0] = arr[0];
 
    for (int i = 1; i < N; i++)
        pref[i] = pref[i - 1] + arr[i];
 
    // Declare map to store count of
    // elements upto current element
    map<int, int> mp;
    int answer = 0;
 
    // To count all the subarrays
    // whose prefix sum is 0
    mp[0]++;
 
    // Iterate the array
    for (int i = 0; i < N; i++) {
 
        // Increment answer by count of
        // current element of prefix array
        answer += mp[pref[i]];
        mp[pref[i]]++;
    }
 
    // Return the answer
    return answer;
}
 
// Driver Code
int main()
{
    // Given array arr[]
    int arr[] = { 1, 1, 0 };
    int N = sizeof arr / sizeof arr[0];
 
    // Function call
    cout << countOfSubarray(arr, N);
    return 0;
}

// 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 int countOfSubarray(int arr[], int N)
{
    // Decrementing all the elements
    // of the array by 1
    for (int i = 0; i < N; i++)
        arr[i]--;
 
    // Making prefix sum array
    int []pref = new int[N];
    pref[0] = arr[0];
 
    for (int i = 1; i < N; i++)
        pref[i] = pref[i - 1] + arr[i];
 
    // Declare map to store count of
    // elements upto current element
    HashMap<Integer,
              Integer> mp = new HashMap<Integer,
                                        Integer>();
    int answer = 0;
 
    // To count all the subarrays
    // whose prefix sum is 0
    mp.put(0, 1);
 
    // Iterate the array
    for (int i = 0; i < N; i++)
    {
 
        // Increment answer by count of
        // current element of prefix array
 
        if(mp.containsKey(pref[i]))
        {
            answer += mp.get(pref[i]);
            mp.put(pref[i], mp.get(pref[i]) + 1);
             
        }
        else
        {
            mp.put(pref[i], 1);
        }
    }
 
    // Return the answer
    return answer;
}
 
// Driver Code
public static void main(String[] args)
{
    // Given array arr[]
    int arr[] = { 1, 1, 0 };
    int N = arr.length;
 
    // Function call
    System.out.print(countOfSubarray(arr, N));
}
}
 
// This code is contributed by sapnasingh4991

# 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):
 
    # Decrementing all the elements
    # of the array by 1
    for i in range(N):
        arr[i] -= 1
 
    # Making prefix sum array
    pref = [0] * N
    pref[0] = arr[0]
 
    for i in range(1, N):
        pref[i] = pref[i - 1] + arr[i]
 
    # Declare map to store count of
    # elements upto current element
    mp = defaultdict(lambda : 0)
    answer = 0
 
    # To count all the subarrays
    # whose prefix sum is 0
    mp[0] += 1
 
    # Iterate the array
    for i in range(N):
 
        # Increment answer by count of
        # current element of prefix array
        answer += mp[pref[i]]
        mp[pref[i]] += 1
 
    # Return the answer
    return answer
 
# Driver Code
 
# Given array arr[]
arr = [ 1, 1, 0 ]
N = len(arr)
 
# Function call
print(countOfSubarray(arr, N))
 
# This code is contributed by Shivam Singh

// 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 int countOfSubarray(int []arr, int N)
{
    // Decrementing all the elements
    // of the array by 1
    for (int i = 0; i < N; i++)
        arr[i]--;
 
    // Making prefix sum array
    int []pref = new int[N];
    pref[0] = arr[0];
 
    for (int i = 1; i < N; i++)
        pref[i] = pref[i - 1] + arr[i];
 
    // Declare map to store count of
    // elements upto current element
    Dictionary<int,
               int> mp = new Dictionary<int,
                                        int>();
    int answer = 0;
 
    // To count all the subarrays
    // whose prefix sum is 0
    mp.Add(0, 1);
 
    // Iterate the array
    for (int i = 0; i < N; i++)
    {
 
        // Increment answer by count of
        // current element of prefix array
 
        if(mp.ContainsKey(pref[i]))
        {
            answer += mp[pref[i]];
            mp[pref[i]]= mp[pref[i]] + 1;   
        }
        else
        {
            mp.Add(pref[i], 1);
        }
    }
 
    // Return the answer
    return answer;
}
 
// Driver Code
public static void Main(String[] args)
{
    // Given array []arr
    int []arr = { 1, 1, 0 };
    int N = arr.Length;
 
    // Function call
    Console.Write(countOfSubarray(arr, N));
}
}
 
// This code is contributed by sapnasingh4991

<script>
// Js program for the above approach
 
// Function that counts the subarrays
// with sum of its elements as its length
function countOfSubarray( arr, N){
    // Decrementing all the elements
    // of the array by 1
    for (let i = 0; i < N; i++)
        arr[i]--;
 
    // Making prefix sum array
    let pref = [];
    pref[0] = arr[0];
 
    for (let i = 1; i < N; i++)
        pref[i] = pref[i - 1] + arr[i];
 
    // Declare map to store count of
    // elements upto current element
    let mp = new Map;
    let answer = 0;
 
    // To count all the subarrays
    // whose prefix sum is 0
    if(mp[0])
    mp[0]++;
    else
    mp[0] = 1;
 
    // Iterate the array
    for (let i = 0; i < N; i++) {
        // Increment answer by count of
        // current element of prefix array
        if(mp[pref[i]]){
        answer += mp[pref[i]];
        mp[pref[i]]++;
        }
    }
 
    // Return the answer
    return answer;
}
 
// Driver Code
// Given array arr[]
let arr = [ 1, 1, 0 ];
let N = arr.length;
// Function call
document.write(countOfSubarray(arr, N));
 
</script>

3

Complejidad de tiempo: O(N * Log(N))
Espacio auxiliar: O(N)