Subarreglo de tamaño k con suma dada

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

Publicación traducida automáticamente

Artículo escrito por barykrg 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 *