Dada una array no ordenada de enteros, encuentre el número de subarreglos que tienen una suma exactamente igual a un número k dado.
Ejemplos:
Entrada: arr[] = {10, 2, -2, -20, 10}, k = -10
Salida: 3
Explicación: Subarreglos: arr[0…3], arr[1…4], arr[3.. 4] tienen una suma exactamente igual a -10.Entrada: arr[] = {9, 4, 20, 3, 10, 5}, k = 33
Salida: 2
Explicación: Los subarreglos: arr[0…2], arr[2…4] tienen una suma exactamente igual a 33 .
Solución ingenua: una solución simple es recorrer todos los subarreglos y calcular su suma. Si la suma es igual a la suma requerida, incremente el recuento de subarreglos. Imprime el recuento final del subarreglo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
int main()
{
int arr[] = {10, 2, -2, -20, 10};
int k = -10;
int n = sizeof(arr) / sizeof(arr[0]);
int res = 0;
// Calculate all subarrays
for (int i = 0; i < n; i++)
{
int sum = 0;
for (int j = i; j < n; j++)
{
// Calculate required sum
sum += arr[j];
// Check if sum is equal to required sum
if (sum == k)
res++;
}
}
cout << (res) << endl;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program for the above approach
#include <stdio.h>
int main()
{
int arr[] = { 10, 2, -2, -20, 10 };
int k = -10;
int n = sizeof(arr) / sizeof(arr[0]);
int res = 0;
// Calculate all subarrays
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = i; j < n; j++)
{
// Calculate required sum
sum += arr[j];
// Check if sum is equal to required sum
if (sum == k)
res++;
}
}
printf("%d\n", res);
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program for the above approach
import java.util.*;
class Solution {
public static void main(String[] args)
{
int arr[] = { 10, 2, -2, -20, 10 };
int k = -10;
int n = arr.length;
int res = 0;
// calculate all subarrays
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = i; j < n; j++) {
// calculate required sum
sum += arr[j];
// check if sum is equal to required sum
if (sum == k)
res++;
}
}
System.out.println(res);
}
}
// This code is contributed by Aditya Kumar (adityakumar129)
Python3
# Python3 program for # the above approach arr = [ 10, 2, -2, -20, 10 ] n = len(arr) k = -10 res = 0 # Calculate all subarrays for i in range(n): summ = 0 for j in range(i, n): # Calculate required sum summ += arr[j] # Check if sum is equal to # required sum if summ == k: res += 1 print(res) # This code is contributed by kavan155gondalia
C#
// C# program for
// the above approach
using System;
using System.Collections.Generic;
class GFG {
static void Main() {
int[] arr = {10, 2, -2, -20, 10};
int k = -10;
int n = arr.Length;
int res = 0;
// Calculate all subarrays
for (int i = 0; i < n; i++)
{
int sum = 0;
for (int j = i; j < n; j++)
{
// Calculate required sum
sum += arr[j];
// Check if sum is equal to
// required sum
if (sum == k)
res++;
}
}
Console.WriteLine(res);
}
}
// This code is contributed by divyesh072019
Javascript
<script>
// Javascript program for
// the above approach
let arr = [ 10, 2, -2, -20, 10 ];
let k = -10;
let n = arr.length;
let res = 0;
// Calculate all subarrays
for(let i = 0; i < n; i++)
{
let sum = 0;
for(let j = i; j < n; j++)
{
// Calculate required sum
sum += arr[j];
// Check if sum is equal to
// required sum
if (sum == k)
res++;
}
}
document.write(res);
// This code is contributed by suresh07
</script>
3
Complejidad del tiempo : O(n 2 )
Espacio Auxiliar: O(1)
Solución eficiente:Una solución eficiente es mientras se recorre la array, almacenando la suma hasta ahora en currsum. Además, mantenga el recuento de diferentes valores de currsum en un mapa. Si el valor de currsum es igual a la suma deseada en cualquier instancia, incremente el recuento de subarreglos en uno. El valor de currsum excede la suma deseada por currsum – sum. Si este valor se elimina de currsum, se puede obtener la suma deseada. En el mapa, encuentre el número de subarreglos encontrados previamente que tienen una suma igual a currsum-sum. Excluyendo todos esos subarreglos del subarreglo actual, da nuevos subarreglos que tienen la suma deseada. Así que aumente el conteo por el número de dichos subarreglos. Tenga en cuenta que cuando currsum es igual a la suma deseada, también verifique la cantidad de subarreglos que anteriormente tenían una suma igual a 0. Excluyendo esos subarreglos del subarreglo actual da nuevos subarreglos que tienen la suma deseada. Aumente el conteo por el número de subarreglos que tengan suma 0 en ese caso.
C++
// C++ program to find number of subarrays with sum exactly
// equal to k.
#include <bits/stdc++.h>
using namespace std;
// Function to find number of subarrays with sum exactly
// equal to k.
int findSubarraySum(int arr[], int n, int sum)
{
// STL map to store number of subarrays starting from
// index zero having particular value of sum.
unordered_map<int, int> prevSum;
int res = 0;
// Sum of elements so far.
int currSum = 0;
for (int i = 0; i < n; i++) {
// Add current element to sum so far.
currSum += arr[i];
// If currsum is equal to desired sum, then a new
// subarray is found. So increase count of
// subarrays.
if (currSum == sum)
res++;
// currsum exceeds given sum by currsum - sum. Find
// number of subarrays having this sum and exclude
// those subarrays from currsum by increasing count
// by same amount.
if (prevSum.find(currSum - sum) != prevSum.end())
res += (prevSum[currSum - sum]);
// Add currsum value to count of different values of
// sum.
prevSum[currSum]++;
}
return res;
}
int main()
{
int arr[] = { 10, 2, -2, -20, 10 };
int sum = -10;
int n = sizeof(arr) / sizeof(arr[0]);
cout << findSubarraySum(arr, n, sum);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to find number of subarrays
// with sum exactly equal to k.
import java.util.HashMap;
import java.util.Map;
public class GfG {
// Function to find number of subarrays
// with sum exactly equal to k.
static int findSubarraySum(int arr[], int n, int sum)
{
// HashMap to store number of subarrays
// starting from index zero having
// particular value of sum.
HashMap<Integer, Integer> prevSum = new HashMap<>();
prevSum.put(0,1);
int res = 0;
// Sum of elements so far.
int currSum = 0;
for (int i = 0; i < n; i++) {
// Add current element to sum so far.
currSum += arr[i];
//calculate the sum that have to be removed
//so that we can get the desired sum
int removeSum=currSum-sum;
//get count of occurrences of that sum that
//have to removed and add it to res value
if (prevSum.containsKey(removeSum))
res += prevSum.get(removeSum);
// Add currsum value to count of
// different values of sum.
prevSum.put(currSum,prevSum.getOrDefault(currSum,0)+1);
}
return res;
}
public static void main(String[] args)
{
int arr[] = { 10, 2, -2, -20, 10 };
int sum = -10;
int n = arr.length;
System.out.println(findSubarraySum(arr, n, sum));
}
}
// This code is contributed by Rituraj Jain
Python3
# Python3 program to find the number of # subarrays with sum exactly equal to k. from collections import defaultdict # Function to find number of subarrays # with sum exactly equal to k. def findSubarraySum(arr, n, Sum): # Dictionary to store number of subarrays # starting from index zero having # particular value of sum. prevSum = defaultdict(lambda : 0) res = 0 # Sum of elements so far. currsum = 0 for i in range(0, n): # Add current element to sum so far. currsum += arr[i] # If currsum is equal to desired sum, # then a new subarray is found. So # increase count of subarrays. if currsum == Sum: res += 1 # currsum exceeds given sum by currsum - sum. # Find number of subarrays having # this sum and exclude those subarrays # from currsum by increasing count by # same amount. if (currsum - Sum) in prevSum: res += prevSum[currsum - Sum] # Add currsum value to count of # different values of sum. prevSum[currsum] += 1 return res if __name__ == "__main__": arr = [10, 2, -2, -20, 10] Sum = -10 n = len(arr) print(findSubarraySum(arr, n, Sum)) # This code is contributed by Rituraj Jain
C#
// C# program to find number of subarrays
// with sum exactly equal to k.
using System;
using System.Collections.Generic;
class GFG {
// Function to find number of subarrays
// with sum exactly equal to k.
public static int findSubarraySum(int[] arr,
int n, int sum)
{
// HashMap to store number of subarrays
// starting from index zero having
// particular value of sum.
Dictionary<int, int> prevSum = new Dictionary<int, int>();
int res = 0;
// Sum of elements so far
int currsum = 0;
for (int i = 0; i < n; i++) {
// Add current element to sum so far.
currsum += arr[i];
// If currsum is equal to desired sum,
// then a new subarray is found. So
// increase count of subarrays.
if (currsum == sum)
res++;
// currsum exceeds given sum by currsum
// - sum. Find number of subarrays having
// this sum and exclude those subarrays
// from currsum by increasing count by
// same amount.
if (prevSum.ContainsKey(currsum - sum))
res += prevSum[currsum - sum];
// Add currsum value to count of
// different values of sum.
if (!prevSum.ContainsKey(currsum))
prevSum.Add(currsum, 1);
else {
int count = prevSum[currsum];
prevSum[currsum] = count + 1;
}
}
return res;
}
// Driver Code
public static void Main()
{
int[] arr = { 10, 2, -2, -20, 10 };
int sum = -10;
int n = arr.Length;
Console.Write(findSubarraySum(arr, n, sum));
}
}
// This code is contributed by
// sanjeev2552
Javascript
<script>
// Javascript program to find number of subarrays
// with sum exactly equal to k.
// Function to find number of subarrays
// with sum exactly equal to k.
function findSubarraySum(arr,n,sum)
{
// HashMap to store number of subarrays
// starting from index zero having
// particular value of sum.
let prevSum = new Map();
let res = 0;
// Sum of elements so far.
let currsum = 0;
for (let i = 0; i < n; i++)
{
// Add current element to sum so far.
currsum += arr[i];
// If currsum is equal to desired sum,
// then a new subarray is found. So
// increase count of subarrays.
if (currsum == sum)
res++;
// currsum exceeds given sum by currsum
// - sum. Find number of subarrays having
// this sum and exclude those subarrays
// from currsum by increasing count by
// same amount.
if (prevSum.has(currsum - sum))
res += prevSum.get(currsum - sum);
// Add currsum value to count of
// different values of sum.
let count = prevSum.get(currsum);
if (count == null)
prevSum.set(currsum, 1);
else
prevSum.set(currsum, count + 1);
}
return res;
}
let arr = [10, 2, -2, -20, 10];
let sum = -10;
let n = arr.length;
document.write(findSubarraySum(arr, n, sum));
// This code is contributed by avanitrachhadiya2155.
</script>
3
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Este artículo es una contribución de Aarti_Rathi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.