Dada una array arr[] de enteros positivos y un rango (L, R). Encuentre el número de subarreglos que tienen una suma en el rango L a R.
Ejemplos:
Input : arr[] = {1, 4, 6}, L = 3, R = 8
Output : 3
The subarrays are {1, 4}, {4}, {6}.
Input : arr[] = {2, 3, 5, 8}, L = 4, R = 13
Output : 6
The subarrays are {2, 3}, {2, 3, 5}, {3, 5},
{5}, {5, 8}, {8}.
Una solución simple es considerar uno por uno cada subarreglo y encontrar su suma. Si la suma se encuentra en el rango [L, R], incremente el conteo. La complejidad temporal de esta solución es O(n^2).
Una solución eficiente es encontrar primero el número de subarreglos que tienen una suma menor o igual que R. De este recuento, reste el número de subarreglos que tienen una suma menor o igual que L-1. Para encontrar el número de subarreglos que tienen una suma menor o igual que el valor dado, se usa el método de tiempo lineal usando la ventana deslizante que se analiza en la siguiente publicación:
Número de subarreglos que tienen una suma menor o igual que k .
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find number of subarrays having
// sum in the range L to R.
#include <bits/stdc++.h>
using namespace std;
// Function to find number of subarrays having
// sum less than or equal to x.
int countSub(int arr[], int n, int x)
{
// Starting index of sliding window.
int st = 0;
// Ending index of sliding window.
int end = 0;
// Sum of elements currently present
// in sliding window.
int sum = 0;
// To store required number of subarrays.
int cnt = 0;
// Increment ending index of sliding
// window one step at a time.
while (end < n) {
// Update sum of sliding window on
// adding a new element.
sum += arr[end];
// Increment starting index of sliding
// window until sum is greater than x.
while (st <= end && sum > x) {
sum -= arr[st];
st++;
}
// Update count of number of subarrays.
cnt += (end - st + 1);
end++;
}
return cnt;
}
// Function to find number of subarrays having
// sum in the range L to R.
int findSubSumLtoR(int arr[], int n, int L, int R)
{
// Number of subarrays having sum less
// than or equal to R.
int Rcnt = countSub(arr, n, R);
// Number of subarrays having sum less
// than or equal to L-1.
int Lcnt = countSub(arr, n, L - 1);
return Rcnt - Lcnt;
}
// Driver code.
int main()
{
int arr[] = { 1, 4, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
int L = 3;
int R = 8;
cout << findSubSumLtoR(arr, n, L, R);
return 0;
}
Java
// Java program to find number
// of subarrays having sum in
// the range L to R.
import java.io.*;
class GFG
{
// Function to find number
// of subarrays having sum
// less than or equal to x.
static int countSub(int arr[],
int n, int x)
{
// Starting index of
// sliding window.
int st = 0;
// Ending index of
// sliding window.
int end = 0;
// Sum of elements currently
// present in sliding window.
int sum = 0;
// To store required
// number of subarrays.
int cnt = 0;
// Increment ending index
// of sliding window one
// step at a time.
while (end < n)
{
// Update sum of sliding
// window on adding a
// new element.
sum += arr[end];
// Increment starting index
// of sliding window until
// sum is greater than x.
while (st <= end && sum > x)
{
sum -= arr[st];
st++;
}
// Update count of
// number of subarrays.
cnt += (end - st + 1);
end++;
}
return cnt;
}
// Function to find number
// of subarrays having sum
// in the range L to R.
static int findSubSumLtoR(int arr[], int n,
int L, int R)
{
// Number of subarrays
// having sum less than
// or equal to R.
int Rcnt = countSub(arr, n, R);
// Number of subarrays
// having sum less than
// or equal to L-1.
int Lcnt = countSub(arr, n, L - 1);
return Rcnt - Lcnt;
}
// Driver code
public static void main (String[] args)
{
int arr[] = { 1, 4, 6 };
int n = arr.length;
int L = 3;
int R = 8;
System.out.println(findSubSumLtoR(arr, n, L, R));
}
}
// This code is contributed
// by Mahadev99
C#
// C# program to find number
// of subarrays having sum in
// the range L to R.
using System;
class GFG
{
// Function to find number
// of subarrays having sum
// less than or equal to x.
static int countSub(int[] arr,
int n, int x)
{
// Starting index of
// sliding window.
int st = 0;
// Ending index of
// sliding window.
int end = 0;
// Sum of elements currently
// present in sliding window.
int sum = 0;
// To store required
// number of subarrays.
int cnt = 0;
// Increment ending index
// of sliding window one
// step at a time.
while (end < n)
{
// Update sum of sliding
// window on adding a
// new element.
sum += arr[end];
// Increment starting index
// of sliding window until
// sum is greater than x.
while (st <= end && sum > x)
{
sum -= arr[st];
st++;
}
// Update count of
// number of subarrays.
cnt += (end - st + 1);
end++;
}
return cnt;
}
// Function to find number
// of subarrays having sum
// in the range L to R.
static int findSubSumLtoR(int[] arr, int n,
int L, int R)
{
// Number of subarrays
// having sum less than
// or equal to R.
int Rcnt = countSub(arr, n, R);
// Number of subarrays
// having sum less than
// or equal to L-1.
int Lcnt = countSub(arr, n, L - 1);
return Rcnt - Lcnt;
}
// Driver code
public static void Main ()
{
int[] arr = { 1, 4, 6 };
int n = arr.Length;
int L = 3;
int R = 8;
Console.Write(findSubSumLtoR(arr, n, L, R));
}
}
// This code is contributed
// by ChitraNayal
Python 3
# Python 3 program to find # number of subarrays having # sum in the range L to R. # Function to find number # of subarrays having sum # less than or equal to x. def countSub(arr, n, x): # Starting index of # sliding window. st = 0 # Ending index of # sliding window. end = 0 # Sum of elements currently # present in sliding window. sum = 0 # To store required # number of subarrays. cnt = 0 # Increment ending index # of sliding window one # step at a time. while end < n : # Update sum of sliding # window on adding a # new element. sum += arr[end] # Increment starting index # of sliding window until # sum is greater than x. while (st <= end and sum > x) : sum -= arr[st] st += 1 # Update count of # number of subarrays. cnt += (end - st + 1) end += 1 return cnt # Function to find number # of subarrays having sum # in the range L to R. def findSubSumLtoR(arr, n, L, R): # Number of subarrays # having sum less # than or equal to R. Rcnt = countSub(arr, n, R) # Number of subarrays # having sum less than # or equal to L-1. Lcnt = countSub(arr, n, L - 1) return Rcnt - Lcnt # Driver code arr = [ 1, 4, 6 ] n = len(arr) L = 3 R = 8 print(findSubSumLtoR(arr, n, L, R)) # This code is contributed # by ChitraNayal
PHP
<?php
// PHP program to find number
// of subarrays having sum
// in the range L to R.
// Function to find number
// of subarrays having sum
// less than or equal to x.
function countSub(&$arr, $n, $x)
{
// Starting index of
// sliding window.
$st = 0;
// Ending index of
// sliding window.
$end = 0;
// Sum of elements currently
// present in sliding window.
$sum = 0;
// To store required
// number of subarrays.
$cnt = 0;
// Increment ending index
// of sliding window one
// step at a time.
while ($end < $n)
{
// Update sum of sliding window
// on adding a new element.
$sum += $arr[$end];
// Increment starting index
// of sliding window until
// sum is greater than x.
while ($st <= $end && $sum > $x)
{
$sum -= $arr[$st];
$st++;
}
// Update count of
// number of subarrays.
$cnt += ($end - $st + 1);
$end++;
}
return $cnt;
}
// Function to find number
// of subarrays having sum
// in the range L to R.
function findSubSumLtoR(&$arr, $n, $L, $R)
{
// Number of subarrays
// having sum less
// than or equal to R.
$Rcnt = countSub($arr, $n, $R);
// Number of subarrays
// having sum less
// than or equal to L-1.
$Lcnt = countSub($arr, $n, $L - 1);
return $Rcnt - $Lcnt;
}
// Driver code.
$arr = array( 1, 4, 6 );
$n = sizeof($arr);
$L = 3;
$R = 8;
echo findSubSumLtoR($arr, $n, $L, $R);
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// Javascript program to find number of subarrays having
// sum in the range L to R.
// Function to find number of subarrays having
// sum less than or equal to x.
function countSub(arr, n, x)
{
// Starting index of sliding window.
var st = 0;
// Ending index of sliding window.
var end = 0;
// Sum of elements currently present
// in sliding window.
var sum = 0;
// To store required number of subarrays.
var cnt = 0;
// Increment ending index of sliding
// window one step at a time.
while (end < n) {
// Update sum of sliding window on
// adding a new element.
sum += arr[end];
// Increment starting index of sliding
// window until sum is greater than x.
while (st <= end && sum > x) {
sum -= arr[st];
st++;
}
// Update count of number of subarrays.
cnt += (end - st + 1);
end++;
}
return cnt;
}
// Function to find number of subarrays having
// sum in the range L to R.
function findSubSumLtoR(arr, n, L, R)
{
// Number of subarrays having sum less
// than or equal to R.
var Rcnt = countSub(arr, n, R);
// Number of subarrays having sum less
// than or equal to L-1.
var Lcnt = countSub(arr, n, L - 1);
return Rcnt - Lcnt;
}
// Driver code.
var arr = [ 1, 4, 6 ];
var n = arr.length;
var L = 3;
var R = 8;
document.write( findSubSumLtoR(arr, n, L, R));
</script>
Producción:
3
Complejidad temporal: O(n)
Espacio auxiliar: O(1)