Dada una array arr[], un entero K y una Suma. La tarea es verificar si existe algún subarreglo con K elementos cuya suma sea igual a la suma dada. Si alguno de los subarreglo con tamaño K tiene la suma igual a la suma dada, imprima SÍ; de lo contrario, imprima NO.
Ejemplos :
Input: arr[] = {1, 4, 2, 10, 2, 3, 1, 0, 20}
k = 4, sum = 18
Output: YES
Subarray = {4, 2, 10, 2}
Input: arr[] = {1, 4, 2, 10, 2, 3, 1, 0, 20}
k = 3, sum = 6
Output: YES
Una solución simple es usar bucles anidados, donde verificamos cada subarreglo de tamaño k.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to check if any Subarray of size
// K has a given Sum
#include <iostream>
using namespace std;
// Function to check if any Subarray of size K
// has a given Sum
bool checkSubarraySum(int arr[], int n,
int k, int sum)
{
// Consider all blocks starting with i.
for (int i = 0; i < n - k + 1; i++) {
int current_sum = 0;
// Consider each subarray of size k
for (int j = 0; j < k; j++)
current_sum = current_sum + arr[i + j];
if (current_sum == sum)
return true;
}
return false;
}
// Driver code
int main()
{
int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };
int k = 4;
int sum = 18;
int n = sizeof(arr) / sizeof(arr[0]);
if (checkSubarraySum(arr, n, k, sum))
cout << "YES";
else
cout << "NO";
return 0;
}
Java
// Java program to check
// if any Subarray of size
// K has a given Sum
class GFG
{
// Function to check if any
// Subarray of size K has
// a given Sum
static boolean checkSubarraySum(int arr[], int n,
int k, int sum)
{
// Consider all blocks
// starting with i.
for (int i = 0; i < n - k + 1; i++)
{
int current_sum = 0;
// Consider each
// subarray of size k
for (int j = 0; j < k; j++)
current_sum = current_sum +
arr[i + j];
if (current_sum == sum)
return true;
}
return false;
}
// Driver code
public static void main(String args[])
{
int arr[] = new int[] { 1, 4, 2, 10, 2,
3, 1, 0, 20 };
int k = 4;
int sum = 18;
int n = arr.length;
if (checkSubarraySum(arr, n, k, sum))
System.out.println("YES");
else
System.out.println("NO");
}
}
// This code is contributed
// by Kirti_Mangal
Python3
# Python3 program to check
# if any Subarray of size
# K has a given Sum
# Function to check if
# any Subarray of size
# K, has a given Sum
def checkSubarraySum(arr, n, k, sum):
# Consider all blocks
# starting with i.
for i in range (n - k + 1):
current_sum = 0;
# Consider each subarray
# of size k
for j in range(k):
current_sum = (current_sum +
arr[i + j]);
if (current_sum == sum):
return True;
return False;
# Driver code
arr = [1, 4, 2, 10, 2,
3, 1, 0, 20];
k = 4;
sum = 18;
n = len(arr);
if (checkSubarraySum(arr, n, k, sum)):
print("YES");
else:
print("NO");
# This code is contributed by mits
C#
// C# program to check if any
// Subarray of size K has a given Sum
using System;
class GFG
{
// Function to check if any Subarray
// of size K has a given Sum
static bool checkSubarraySum(int[] arr, int n,
int k, int sum)
{
// Consider all blocks
// starting with i.
for (int i = 0; i < n - k + 1; i++)
{
int current_sum = 0;
// Consider each
// subarray of size k
for (int j = 0; j < k; j++)
current_sum = current_sum +
arr[i + j];
if (current_sum == sum)
return true;
}
return false;
}
// Driver code
static void Main()
{
int[] arr = new int[] { 1, 4, 2, 10,
2, 3, 1, 0, 20 };
int k = 4;
int sum = 18;
int n = arr.Length;
if (checkSubarraySum(arr, n, k, sum))
Console.WriteLine("YES");
else
Console.WriteLine("NO");
}
}
// This code is contributed
// by mits
PHP
<?php
// PHP program to check
// if any Subarray of size
// K has a given Sum
// Function to check if
// any Subarray of size
// K, has a given Sum
function checkSubarraySum($arr, $n,
$k, $sum)
{
// Consider all blocks starting with i.
for ($i = 0; $i < $n - $k + 1; $i++)
{
$current_sum = 0;
// Consider each subarray of size k
for ($j = 0; $j < $k; $j++)
$current_sum = $current_sum +
$arr[$i + $j];
if ($current_sum == $sum)
return true;
}
return false;
}
// Driver code
$arr = array(1, 4, 2, 10, 2,
3, 1, 0, 20);
$k = 4;
$sum = 18;
$n = sizeof($arr);
if (checkSubarraySum($arr, $n,
$k, $sum))
echo "YES";
else
echo "NO";
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program to check if any
// Subarray of size K has a given Sum
// Function to check if any Subarray
// of size K has a given Sum
function checkSubarraySum(arr, n, k, sum)
{
// Consider all blocks
// starting with i.
for (let i = 0; i < n - k + 1; i++)
{
let current_sum = 0;
// Consider each
// subarray of size k
for (let j = 0; j < k; j++)
current_sum = current_sum + arr[i + j];
if (current_sum == sum)
return true;
}
return false;
}
let arr = [ 1, 4, 2, 10, 2, 3, 1, 0, 20 ];
let k = 4;
let sum = 18;
let n = arr.length;
if (checkSubarraySum(arr, n, k, sum))
document.write("YES");
else
document.write("NO");
// This code is contributed by mukesh07.
</script>
Producción:
YES
Complejidad de tiempo : O(n * k)
Una solución eficiente es verificar la técnica de la ventana deslizante y verificar simultáneamente si la suma es igual a la suma dada.
C++
// CPP program to check if any Subarray of size
// K has a given Sum
#include <iostream>
using namespace std;
// Function to check if any Subarray of size K
// has a given Sum
bool checkSubarraySum(int arr[], int n,
int k, int sum)
{
// Check for first window
int curr_sum = 0;
for (int i=0; i<k; i++)
curr_sum += arr[i];
if (curr_sum == sum)
return true;
// Consider remaining blocks ending with j
for (int j = k; j < n; j++) {
curr_sum = curr_sum + arr[j] - arr[j-k];
if (curr_sum == sum)
return true;
}
return false;
}
// Driver code
int main()
{
int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };
int k = 4;
int sum = 18;
int n = sizeof(arr) / sizeof(arr[0]);
if (checkSubarraySum(arr, n, k, sum))
cout << "YES";
else
cout << "NO";
return 0;
}
Java
// Java program to check if any Subarray of size
// K has a given Sum
class GFG{
// Function to check if any Subarray of size K
// has a given Sum
static boolean checkSubarraySum(int[] arr, int n,
int k, int sum)
{
// Check for first window
int curr_sum = 0;
for (int i=0; i<k; i++)
curr_sum += arr[i];
if (curr_sum == sum)
return true;
// Consider remaining blocks ending with j
for (int j = k; j < n; j++) {
curr_sum = curr_sum + arr[j] - arr[j-k];
if (curr_sum == sum)
return true;
}
return false;
}
// Driver code
public static void main(String[] args)
{
int[] arr=new int[]{ 1, 4, 2, 10, 2, 3, 1, 0, 20 };
int k = 4;
int sum = 18;
int n = arr.length;
if (checkSubarraySum(arr, n, k, sum))
System.out.println("YES");
else
System.out.println("NO");
}
}
// This code is contributed by mits
Python3
# Python3 program to check if any
# Subarray of size K has a given Sum
# Function to check if any Subarray
# of size K has a given Sum
def checkSubarraySum(arr, n,
k, sumV):
# Check for first window
curr_sum = 0
for i in range(0, k):
curr_sum += arr[i]
if (curr_sum == sumV):
return true
# Consider remaining blocks
# ending with j
for j in range(k, n):
curr_sum = (curr_sum + arr[j] -
arr[j - k])
if (curr_sum == sumV) :
return True
return False
# Driver code
arr = [ 1, 4, 2, 10, 2,
3, 1, 0, 20 ]
k = 4
sumV = 18
n = len(arr)
if (checkSubarraySum(arr, n, k, sumV)):
print("YES")
else:
print( "NO")
# This code is contributed
# by Yatin Gupta
C#
// C# program to check if any Subarray of size
// K has a given Sum
using System;
class GFG{
// Function to check if any Subarray of size K
// has a given Sum
static bool checkSubarraySum(int[] arr, int n,
int k, int sum)
{
// Check for first window
int curr_sum = 0;
for (int i=0; i<k; i++)
curr_sum += arr[i];
if (curr_sum == sum)
return true;
// Consider remaining blocks ending with j
for (int j = k; j < n; j++) {
curr_sum = curr_sum + arr[j] - arr[j-k];
if (curr_sum == sum)
return true;
}
return false;
}
// Driver code
static void Main()
{
int[] arr=new int[]{ 1, 4, 2, 10, 2, 3, 1, 0, 20 };
int k = 4;
int sum = 18;
int n = arr.Length;
if (checkSubarraySum(arr, n, k, sum))
Console.WriteLine("YES");
else
Console.WriteLine("NO");
}
}
// This code is contributed by mits
PHP
<?php
// PHP program to check if any
// Subarray of size K has a given Sum
// Function to check if any Subarray
// of size K has a given Sum
function checkSubarraySum($arr, $n,
$k, $sum)
{
// Check for first window
$curr_sum = 0;
for ($i = 0; $i < $k; $i++)
$curr_sum += $arr[$i];
if ($curr_sum == $sum)
return true;
// Consider remaining blocks
// ending with j
for ($j = $k; $j < $n; $j++)
{
$curr_sum = $curr_sum + $arr[$j] -
$arr[$j - $k];
if ($curr_sum == $sum)
return true;
}
return false;
}
// Driver code
$arr = array( 1, 4, 2, 10,
2, 3, 1, 0, 20 );
$k = 4;
$sum = 18;
$n = count($arr);
if (checkSubarraySum($arr, $n, $k, $sum))
echo "YES";
else
echo "NO";
// This code is contributed
// by inder_verma
?>
Javascript
<script>
// Javascript program to check if any
// Subarray of size K has a given Sum
// Function to check if any Subarray
// of size K has a given Sum
function checkSubarraySum(arr, n,
k, sum)
{
// Check for first window
let curr_sum = 0;
for (let i = 0; i < k; i++)
curr_sum += arr[i];
if (curr_sum == sum)
return true;
// Consider remaining blocks
// ending with j
for (let j = k; j < n; j++)
{
curr_sum = curr_sum + arr[j] -
arr[j - k];
if (curr_sum == sum)
return true;
}
return false;
}
// Driver code
let arr = new Array( 1, 4, 2, 10,
2, 3, 1, 0, 20 );
let k = 4;
let sum = 18;
let n = arr.length;
if (checkSubarraySum(arr, n, k, sum))
document.write("YES");
else
document.write("NO");
// This code is contributed
// by _saurabh_jaiswal
</script>
Producción:
YES
Complejidad de tiempo : O(n)
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array