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 = 15Entrada: 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