Suma de todos los subarreglos de tamaño K

Dado un arreglo arr[] y un entero K , la tarea es calcular la suma de todos los subarreglos de tamaño K.

Ejemplos: 

Entrada: arr[] = {1, 2, 3, 4, 5, 6}, K = 3 
Salida: 6 9 12 15 
Explicación: 
Todos los subarreglos de tamaño k y su suma: 
Subarreglo 1: {1, 2, 3} = 1 + 2 + 3 = 6 
Subarreglo 2: {2, 3, 4} = 2 + 3 + 4 = 9 
Subarreglo 3: {3, 4, 5} = 3 + 4 + 5 = 12 
Subarreglo 4: {4, 5, 6} = 4 + 5 + 6 = 15

Entrada: arr[] = {1, -2, 3, -4, 5, 6}, K = 2 
Salida: -1, 1, -1, 1, 11 
Explicación: 
Todos los subarreglos de tamaño K y su suma: 
Subarreglo 1: {1, -2} = 1 – 2 = -1 
Subarreglo 2: {-2, 3} = -2 + 3 = -1 
Subarreglo 3: {3, 4} = 3 – 4 = -1 
Subarreglo 4: {-4, 5} = -4 + 5 = 1 
Subarreglo 5: {5, 6} = 5 + 6 = 11 

Enfoque ingenuo: el enfoque ingenuo será generar todos los subarreglos de tamaño K y encontrar la suma de cada subarreglo mediante iteración.

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

C++

// C++ implementation to find the sum
// of all subarrays of size K
  
#include <iostream>
using namespace std;
  
// Function to find the sum of
// all subarrays of size K
int calcSum(int arr[], int n, int k)
{
  
    // Loop to consider every
    // subarray of size K
    for (int i = 0; i <= n - k; i++) {
          
        // Initialize sum = 0
        int sum = 0;
  
        // Calculate sum of all elements
        // of current subarray
        for (int j = i; j < k + i; j++)
            sum += arr[j];
  
        // Print sum of each subarray
        cout << sum << " ";
    }
}
  
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 4, 5, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
  
    // Function Call
    calcSum(arr, n, k);
  
    return 0;
}

Java

// Java implementation to find the sum
// of all subarrays of size K
class GFG{
   
// Function to find the sum of 
// all subarrays of size K
static void calcSum(int arr[], int n, int k)
{
   
    // Loop to consider every 
    // subarray of size K
    for (int i = 0; i <= n - k; i++) {
           
        // Initialize sum = 0
        int sum = 0;
   
        // Calculate sum of all elements
        // of current subarray
        for (int j = i; j < k + i; j++)
            sum += arr[j];
   
        // Print sum of each subarray
        System.out.print(sum+ " ");
    }
}
   
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 1, 2, 3, 4, 5, 6 };
    int n = arr.length;
    int k = 3;
   
    // Function Call
    calcSum(arr, n, k); 
}
}
  
// This code is contributed by Rajput-Ji

C#

// C# implementation to find the sum
// of all subarrays of size K
using System; 
  
class GFG  
{ 
    
    // Function to find the sum of 
    // all subarrays of size K
    static  void calcSum(int[] arr, int n, int k)
    {
      
        // Loop to consider every 
        // subarray of size K
        for (int i = 0; i <= n - k; i++) {
              
            // Initialize sum = 0
            int sum = 0;
      
            // Calculate sum of all elements
            // of current subarray
            for (int j = i; j < k + i; j++)
                sum += arr[j];
      
            // Print sum of each subarray
            Console.Write(sum + " ");
        }
    }
      
    // Driver Code
    static void Main() 
    {
        int[] arr = new int[] { 1, 2, 3, 4, 5, 6 };
        int n = arr.Length;
        int k = 3;
      
        // Function Call
        calcSum(arr, n, k);
      
    }
}
  
// This code is contributed by shubhamsingh10

Python3

# Python3 implementation to find the sum
# of all subarrays of size K
  
# Function to find the sum of
# all subarrays of size K
def calcSum(arr, n, k):
  
    # Loop to consider every
    # subarray of size K
    for i in range(n - k + 1):
          
        # Initialize sum = 0
        sum = 0
  
        # Calculate sum of all elements
        # of current subarray
        for j in range(i, k + i):
            sum += arr[j]
  
        # Print sum of each subarray
        print(sum, end=" ")
  
# Driver Code
arr=[1, 2, 3, 4, 5, 6]
n = len(arr)
k = 3
  
# Function Call
calcSum(arr, n, k)
  
# This code is contributed by mohit kumar 29

Javascript

<script>
  
// JavaScript implementation to find the sum
// of all subarrays of size K
  
// Function to find the sum of 
// all subarrays of size K
function calcSum(arr, n, k)
{
  
    // Loop to consider every 
    // subarray of size K
    for (var i = 0; i <= n - k; i++) {
          
        // Initialize sum = 0
        var sum = 0;
  
        // Calculate sum of all elements
        // of current subarray
        for (var j = i; j < k + i; j++)
            sum += arr[j];
  
        // Print sum of each subarray
        document.write(sum + " ");
    }
}
  
// Driver Code
var arr = [ 1, 2, 3, 4, 5, 6 ];
var n = arr.length;
var k = 3;
  
// Function Call
calcSum(arr, n, k);
  
  
</script>
Producción: 

6 9 12 15

 

Análisis de rendimiento: 

  • Complejidad de tiempo: como en el enfoque anterior, hay dos bucles, donde el primer bucle se ejecuta (N – K) veces y el segundo se ejecuta K veces. Por lo tanto, la complejidad del tiempo será O(N*K) .
  • Complejidad del espacio auxiliar: como en el enfoque anterior. No se utiliza espacio adicional. Por lo tanto, la complejidad del espacio auxiliar será O(1) .

Enfoque eficiente: Uso de ventana deslizante La idea es utilizar el enfoque de ventana deslizante para encontrar la suma de todos los subarreglos posibles en el arreglo.

  • Para cada tamaño en el rango [0, K], busque la suma de la primera ventana de tamaño K y guárdela en una array.
  • Luego, para cada tamaño en el rango [K, N], agregue el siguiente elemento que contribuye a la ventana deslizante y reste el elemento que sobresale de la ventana.
// Adding the element which
// adds into the new window
sum = sum + arr[j]

// Subtracting the element which
// pops out from the window
sum = sum - arr[j-k]

where sum is the variable to store the result
      arr is the given array
      j is the loop variable in range [K, N]

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

C++

// C++ implementation to find the sum
// of all subarrays of size K
  
#include <iostream>
using namespace std;
  
// Function to find the sum of
// all subarrays of size K
int calcSum(int arr[], int n, int k)
{
    // Initialize sum = 0
    int sum = 0;
  
    // Consider first subarray of size k
    // Store the sum of elements
    for (int i = 0; i < k; i++)
        sum += arr[i];
  
    // Print the current sum
    cout << sum << " ";
  
    // Consider every subarray of size k
    // Remove first element and add current
    // element to the window
    for (int i = k; i < n; i++) {
          
        // Add the element which enters
        // into the window and subtract
        // the element which pops out from
        // the window of the size K
        sum = (sum - arr[i - k]) + arr[i];
          
        // Print the sum of subarray
        cout << sum << " ";
    }
}
  
// Drivers Code
int main()
{
    int arr[] = { 1, 2, 3, 4, 5, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
      
    // Function Call
    calcSum(arr, n, k);
  
    return 0;
}

Java

// Java implementation to find the sum
// of all subarrays of size K
class GFG{
  
// Function to find the sum of 
// all subarrays of size K
static void calcSum(int arr[], int n, int k)
{
    // Initialize sum = 0
    int sum = 0;
  
    // Consider first subarray of size k
    // Store the sum of elements
    for (int i = 0; i < k; i++)
        sum += arr[i];
  
    // Print the current sum
    System.out.print(sum+ " ");
  
    // Consider every subarray of size k
    // Remove first element and add current
    // element to the window
    for (int i = k; i < n; i++) {
          
        // Add the element which enters
        // into the window and subtract
        // the element which pops out from
        // the window of the size K
        sum = (sum - arr[i - k]) + arr[i];
          
        // Print the sum of subarray
        System.out.print(sum+ " ");
    }
}
  
// Drivers Code
public static void main(String[] args)
{
    int arr[] = { 1, 2, 3, 4, 5, 6 };
    int n = arr.length;
    int k = 3;
      
    // Function Call
    calcSum(arr, n, k);
}
}
  
// This code is contributed by sapnasingh4991

Python3

# Python3 implementation to find the sum
# of all subarrays of size K
  
# Function to find the sum of
# all subarrays of size K
def calcSum(arr, n, k):
  
    # Initialize sum = 0
    sum = 0
  
    # Consider first subarray of size k
    # Store the sum of elements
    for i in range( k):
        sum += arr[i]
  
    # Print the current sum
    print( sum ,end= " ")
  
    # Consider every subarray of size k
    # Remove first element and add current
    # element to the window
    for i in range(k,n):
          
        # Add the element which enters
        # into the window and subtract
        # the element which pops out from
        # the window of the size K
        sum = (sum - arr[i - k]) + arr[i]
          
        # Print the sum of subarray
        print( sum ,end=" ")
  
# Drivers Code
if __name__ == "__main__":
  
    arr = [ 1, 2, 3, 4, 5, 6 ]
    n = len(arr)
    k = 3
      
    # Function Call
    calcSum(arr, n, k)
  
# This code is contributed by chitranayal

C#

// C# implementation to find the sum
// of all subarrays of size K
using System;
  
class GFG{
   
// Function to find the sum of 
// all subarrays of size K
static void calcSum(int []arr, int n, int k)
{
    // Initialize sum = 0
    int sum = 0;
   
    // Consider first subarray of size k
    // Store the sum of elements
    for (int i = 0; i < k; i++)
        sum += arr[i];
   
    // Print the current sum
    Console.Write(sum+ " ");
   
    // Consider every subarray of size k
    // Remove first element and add current
    // element to the window
    for (int i = k; i < n; i++) {
           
        // Add the element which enters
        // into the window and subtract
        // the element which pops out from
        // the window of the size K
        sum = (sum - arr[i - k]) + arr[i];
           
        // Print the sum of subarray
        Console.Write(sum + " ");
    }
}
   
// Drivers Code
public static void Main(String[] args)
{
    int []arr = { 1, 2, 3, 4, 5, 6 };
    int n = arr.Length;
    int k = 3;
       
    // Function Call
    calcSum(arr, n, k);
}
}
  
// This code is contributed by 29AjayKumar

Javascript

<script>
  
// Javascript implementation to find the sum
// of all subarrays of size K
  
// Function to find the sum of
// all subarrays of size K
function calcSum(arr, n, k)
{
  
    // Initialize sum = 0
    var sum = 0;
  
    // Consider first subarray of size k
    // Store the sum of elements
    for (var i = 0; i < k; i++)
        sum += arr[i];
  
    // Print the current sum
    document.write( sum + " ");
  
    // Consider every subarray of size k
    // Remove first element and add current
    // element to the window
    for (var i = k; i < n; i++) {
          
        // Add the element which enters
        // into the window and subtract
        // the element which pops out from
        // the window of the size K
        sum = (sum - arr[i - k]) + arr[i];
          
        // Print the sum of subarray
        document.write( sum + " ");
    }
}
  
// Drivers Code
var arr = [ 1, 2, 3, 4, 5, 6 ];
var n = arr.length;
var k = 3;
  
// Function Call
calcSum(arr, n, k);
  
// This code is contributed by noob2000.
</script>
Producción: 

6 9 12 15

 

Análisis de rendimiento: 

  • Complejidad del tiempo: como en el enfoque anterior. Hay un bucle que toma el tiempo O (N). Por lo tanto, la Complejidad del Tiempo será O(N) .
  • Complejidad del espacio auxiliar: como en el enfoque anterior. No se utiliza espacio adicional. Por lo tanto, la complejidad del espacio auxiliar será O(1) .
     

Tema relacionado: Subarrays, subsecuencias y subconjuntos en array

Publicación traducida automáticamente

Artículo escrito por spp____ y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *