Recuento de subarreglos que contienen la longitud de ese subarreglo

Dada una array A[] de longitud N , la tarea es contar el número de subarreglos de A[] que contienen la longitud de ese subarreglo.

Ejemplos:

Entrada: A = {10, 11, 1}, N = 3
Salida: 1
Explicación: Sólo el subarreglo {1}, con una longitud de 1, contiene su propia longitud.

Entrada: A = [1, 2, 3, 4, 5], N = 5
Salida: 9
Explicación: Los subarreglos {1}, {1, 2}, {2, 3}, {1, 2, 3}, {2, 3, 4}, {3, 4, 5},  
{1, 2, 3, 4}, {2, 3, 4, 5}, {1, 2, 3, 4, 5} contienen sus propios longitud.

Enfoque: Siga la siguiente idea para resolver el problema:

Primero, forme todos y cada uno de los subarreglos de A. Luego, verifique si la longitud del subarreglo está presente en ese subarreglo.

Siga los pasos mencionados a continuación para implementar la idea:

• Iterar sobre la array de i = 0 a N :
  • Iterar en un bucle anidado de j = i a N :
  • El subarreglo creado es de i a j .
  • Atraviese el subarreglo y verifique si la longitud está presente en el subarreglo.
  • Si está presente, entonces incremente el conteo .
• El conteo final es la respuesta requerida.

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

// C++ code to implement the approach
#include <iostream>
using namespace std;
 
// Function to find the count of the subarrays
// that contain their own length
int findCount(int arr[], int N)
{
    int counts = 0;
 
    // Forming all possible subarrays
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N + 1; j++) {
 
            // Checking if the length is present
            // in the subarray
            for (int k = i; k <= j; k++) {
                if ((j - i) == arr[k])
                    counts += 1;
            }
        }
    }
    return counts;
}
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 4, 5 };
    int N = 5;
 
    // Function Call
    cout << findCount(arr, N);
    return 0;
}
 
// This code is contributed by Rohit Pradhan

// Java code to implement the approach
import java.io.*;
class GFG
{
   
  // Function to find the count of the subarrays
  // that contain their own length
  static int findCount(int[] arr, int N)
  {
    int counts = 0;
 
    // Forming all possible subarrays
    for (int i = 0; i < N; i++) {
      for (int j = i + 1; j < N + 1; j++) {
 
        // Checking if the length is present
        // in the subarray
        for (int k = i; k <= j; k++) {
          if ((j - i) == arr[k])
            counts += 1;
        }
      }
    }
    return counts;
  }
 
  // Driver Code
  public static void main (String[] args) {
    int arr[] = { 1, 2, 3, 4, 5 };
    int N = 5;
 
    // Function Call
    System.out.println( findCount(arr, N));
  }
}
 
// This code is contributed by hrithikgarg03188.

# Python3 code to implement the approach
 
# Function to find the count of the subarrays
# that contain their own length
def findCount(arr, N):
    counts = 0
     
    # Forming all possible subarrays
    for i in range(N):
        for j in range(i + 1, N + 1):
           
            # Checking if the length is present
            # in the subarray
            if j - i in arr[i: j]:
                counts += 1
    return counts
 
 
# Driver Code
if __name__ == '__main__':
    arr = [1, 2, 3, 4, 5]
    N = 5
     
    # Function Call
    print(findCount(arr, N))

// C# code to implement the above approach
using System;
 
public class GFG
{
 
  // Function to find the count of the subarrays
  // that contain their own length
  static int findCount(int[] arr, int N)
  {
    int counts = 0;
 
    // Forming all possible subarrays
    for (int i = 0; i < N; i++) {
      for (int j = i + 1; j < N + 1; j++) {
 
        // Checking if the length is present
        // in the subarray
        for (int k = i; k < j; k++) {
          if ((j - i) == arr[k])
            counts += 1;
        }
      }
    }
    return counts;
  }
 
  // Driver Code
  public static void Main (string[] args) {
    int []arr = { 1, 2, 3, 4, 5 };
    int N = 5;
 
    // Function Call
    Console.WriteLine(findCount(arr, N));
  }
}
 
// This code is contributed by AnkThon

<script>
        // JavaScript code for the above approach
 
        // Function to find the count of the subarrays
        // that contain their own length
        function findCount(arr, N) {
            let counts = 0
 
            // Forming all possible subarrays
            for (let i = 0; i < N; i++) {
                for (let j = i + 1; j < N + 1; j++) {
 
                    // Checking if the length is present
                    // in the subarray
                    for (let k = i; k <= j; k++) {
                        if (arr[k] == j - i) {
                            counts++;
                        }
                    }
                }
            }
            return counts
        }
 
        // Driver Code
 
        let arr = [1, 2, 3, 4, 5]
        let N = 5
 
        // Function Call
        document.write(findCount(arr, N))
    // This code is contributed by Potta Lokesh
    </script>

9

Complejidad temporal: O(N ³ )
Espacio auxiliar: O(1)