Dado un arreglo de enteros positivos y negativos y un entero K. La tarea es encontrar el subarreglo que tiene su suma más cercana a k. En caso de múltiples respuestas, imprima cualquiera.
Nota: Más cercano aquí significa que abs(sum-k) debe ser mínimo.
Ejemplos:
Entrada: a[] = { -5, 12, -3, 4, -15, 6, 1 }, K = 2
Salida: 1
El subarreglo {-3, 4} o {1} tiene sum = 1 que es el más cercano a k.Entrada: a[] = { 2, 2, -1, 5, -3, -2 }, K = 7
Salida: 6
Aquí la salida puede ser 6 u 8
El subarreglo {2, 2, -1, 5} da suma como 8 que tiene abs(8-7) = 1 que es igual a la del subarreglo {2, -1, 5} que tiene abs(6-7) = 1.
Un enfoque ingenuo es verificar todas las sumas de subarreglo posibles usando la suma del prefijo. La complejidad en ese caso será O(N 2 ).
Una solución eficiente será usar el conjunto STL de C++ y la búsqueda binaria para resolver el siguiente problema. Siga el siguiente algoritmo para resolver el problema anterior.
- Inicialmente inserte el primer elemento en el contenedor del conjunto.
- Inicialice la suma de la respuesta como primer elemento y la diferencia como abs(A 0 -k).
- Iterar para todos los elementos de la array de 1 a N y seguir agregando los elementos al prefijo sum en cada paso al contenedor establecido.
- En cada iteración, dado que la suma del prefijo ya está allí, solo necesitamos restar la suma de algunos elementos desde el principio para obtener la suma de cualquier subarreglo. La forma codiciosa será restar la suma del subarreglo que toma la suma más cercana a K.
- Usando la búsqueda binaria ( se puede usar la función lower_bound() ) encuentre la suma del subarreglo desde el principio que está más cerca de (prefijo-k) ya que la resta de ese número de la suma del prefijo dará la suma del subarreglo que está más cerca de K hasta esa iteración .
- También verifique el índice antes del cual devuelve lower_bound(), ya que la suma puede ser mayor o menor que K.
- Si lower_bound no devuelve dicho elemento, la suma del prefijo actual se compara y actualiza si era menor que la suma calculada anteriormente.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to find the
// sum of subarray whose sum is
// closest to K
#include <bits/stdc++.h>
using namespace std;
// Function to find the sum of subarray
// whose sum is closest to K
int closestSubarraySumToK(int a[], int n, int k)
{
// Declare a set
set<int> s;
// initially consider the
// first subarray as the first
// element in the array
int presum = a[0];
// insert
s.insert(a[0]);
// Initially let this difference
// be the minimum
int mini = abs(a[0] - k);
// let this be the sum
// of the subarray
// to be searched initially
int sum = presum;
// iterate for all the array elements
for (int i = 1; i < n; i++) {
// calculate the prefix sum
presum += a[i];
// find the closest subarray
// sum to by using lower_bound
auto it = s.lower_bound(presum - k);
// if it is the first element
// in the set
if (it == s.begin()) {
// get the prefix sum till start
// of the subarray
int diff = *it;
// if the subarray sum is closest to K
// than the previous one
if (abs((presum - diff) - k) < mini) {
// update the minimal difference
mini = abs((presum - diff) - k);
// update the sum
sum = presum - diff;
}
if(abs(presum - k) < mini){
// update the minimal difference
mini = abs((presum - diff) - k);
// update the sum
sum = presum - diff;
}
}
// if the difference is
// present in between
else if (it != s.end()) {
// get the prefix sum till start
// of the subarray
int diff = *it;
// if the subarray sum is closest to K
// than the previous one
if (abs((presum - diff) - k) < mini) {
// update the minimal difference
mini = abs((presum - diff) - k);
// update the sum
sum = presum - diff;
}
// also check for the one before that
// since the sum can be greater than
// or less than K also
it--;
// get the prefix sum till start
// of the subarray
diff = *it;
// if the subarray sum is closest to K
// than the previous one
if (abs((presum - diff) - k) < mini) {
// update the minimal difference
mini = abs((presum - diff) - k);
// update the sum
sum = presum - diff;
}
}
// if there exists no such prefix sum
// then the current prefix sum is
// checked and updated
else {
// if the subarray sum is closest to K
// than the previous one
if (abs(presum - k) < mini) {
// update the minimal difference
mini = abs(presum - k);
// update the sum
sum = presum;
}
}
// insert the current prefix sum
s.insert(presum);
}
return sum;
}
// Driver Code
int main()
{
int a[] = { -5, 12, -3, 4, -15, 6, 1 };
int n = sizeof(a) / sizeof(a[0]);
int k = 2;
cout << closestSubarraySumToK(a, n, k);
return 0;
}
Java
// Java program to find the
// sum of subarray whose sum is
// closest to K
import java.util.*;
class GFG{
// Function to find the sum of subarray
// whose sum is closest to K
static int closestSubarraySumToK(int a[], int n, int k)
{
// Declare a set
TreeSet<Integer> s = new TreeSet<>();
// initially consider the
// first subarray as the first
// element in the array
int presum = a[0];
// insert
s.add(a[0]);
// Initially let this difference
// be the minimum
int mini = Math.abs(a[0] - k);
// let this be the sum
// of the subarray
// to be searched initially
int sum = presum;
// iterate for all the array elements
for (int i = 1; i < n; i++) {
// calculate the prefix sum
presum += a[i];
// find the closest subarray
// sum to by using lower_bound
Integer it = s.lower(presum - k);
// if it is the first element
// in the set
if (it == s.first()) {
// get the prefix sum till start
// of the subarray
int diff = it;
// if the subarray sum is closest to K
// than the previous one
if (Math.abs((presum - diff) - k) < mini) {
// update the minimal difference
mini = Math.abs((presum - diff) - k);
// update the sum
sum = presum - diff;
}
}
// if the difference is
// present in between
else if (it == s.last()) {
// get the prefix sum till start
// of the subarray
int diff = it;
// if the subarray sum is closest to K
// than the previous one
if (Math.abs((presum - diff) - k) < mini) {
// update the minimal difference
mini = Math.abs((presum - diff) - k);
// update the sum
sum = presum - diff;
}
// also check for the one before that
// since the sum can be greater than
// or less than K also
it--;
// get the prefix sum till start
// of the subarray
diff = it;
// if the subarray sum is closest to K
// than the previous one
if (Math.abs((presum - diff) - k) < mini) {
// update the minimal difference
mini = Math.abs((presum - diff) - k);
// update the sum
sum = presum - diff;
}
}
// if there exists no such prefix sum
// then the current prefix sum is
// checked and updated
else {
// if the subarray sum is closest to K
// than the previous one
if (Math.abs(presum - k) < mini) {
// update the minimal difference
mini = Math.abs(presum - k);
// update the sum
sum = presum+1;
}
}
// insert the current prefix sum
s.add(presum);
}
return sum;
}
// Driver Code
public static void main(String[] args)
{
int a[] = { -5, 12, -3, 4, -15, 6, 1 };
int n = a.length;
int k = 2;
System.out.print(closestSubarraySumToK(a, n, k));
}
}
// This code contributed by Rajput-Ji
Python3
# Python3 program to find the # sum of subarray whose sum is # closest to K import bisect # Function to find the sum of subarray # whose sum is closest to K def closestSubarraySumToK(a , n , k): # Declare a set s = [] # initially consider the # first subarray as the first # element in the array presum = a[0] # insert s.append(a[0]) # Initially let this difference # be the minimum mini = abs(a[0] - k) # let this be the sum # of the subarray # to be searched initially sum = presum # iterate for all the array elements for i in range(1, n): # calculate the prefix sum presum += a[i] # find the closest subarray # sum to by using lower_bound it = bisect.bisect_left(s,presum - k) if(it == -1): continue #if it is the first element # in the set if (it == 0): #get the prefix sum till start #of the subarray diff = s[it] # if the subarray sum is closest to K # than the previous one if (abs((presum - diff) - k) < mini): # update the minimal difference mini = abs((presum - diff) - k) # update the sum sum = presum - diff if (abs(presum - k) < mini): #update the minimal difference mini = abs((presum - diff) - k) #update the sum sum = presum - diff # if the difference is # present in between elif (it != len(s)): # get the prefix sum till start # of the subarray diff = s[it] # if the subarray sum is closest to K # than the previous one if (abs((presum - diff) - k) < mini): # update the minimal difference mini = abs((presum - diff) - k) # update the sum sum = presum - diff # also check for the one before that # since the sum can be greater than # or less than K also it -= 1 # get the prefix sum till start # of the subarray diff = s[it] # if the subarray sum is closest to K # than the previous one if (abs((presum - diff) - k) < mini): # update the minimal difference mini = abs((presum - diff) - k) # update the sum sum = presum - diff; # if there exists no such prefix sum # then the current prefix sum is # checked and updated else : # if the subarray sum is closest to K # than the previous one if (abs(presum - k) < mini): # update the minimal difference mini = abs(presum - k) # update the sum sum = presum + 1; # insert the current prefix sum bisect.insort(s, presum) return sum # Driver Code a = [ -5, 12, -3, 4, -15, 6, 1 ] n = len(a) k = 2 print(closestSubarraySumToK(a, n, k)) #This code is contributed by phasing17
C#
// C# program to find the
// sum of subarray whose sum is
// closest to K
using System;
using System.Linq;
using System.Collections.Generic;
public class GFG {
// Function to find the sum of subarray
// whose sum is closest to K
static int closestSubarraySumToK(int []a, int n, int k) {
// Declare a set
SortedSet<int> s = new SortedSet<int>();
// initially consider the
// first subarray as the first
// element in the array
int presum = a[0];
// insert
s.Add(a[0]);
// Initially let this difference
// be the minimum
int mini = Math.Abs(a[0] - k);
// let this be the sum
// of the subarray
// to be searched initially
int sum = presum;
// iterate for all the array elements
for (int i = 1; i < n; i++) {
// calculate the prefix sum
presum += a[i];
// find the closest subarray
// sum to by using lower_bound
int it = lower_bound(s,presum - k);
// if it is the first element
// in the set
if (it == s.First()) {
// get the prefix sum till start
// of the subarray
int diff = it;
// if the subarray sum is closest to K
// than the previous one
if (Math.Abs((presum - diff) - k) < mini) {
// update the minimal difference
mini = Math.Abs((presum - diff) - k);
// update the sum
sum = presum - diff;
}
}
// if the difference is
// present in between
else if (it == s.Last()) {
// get the prefix sum till start
// of the subarray
int diff = it;
// if the subarray sum is closest to K
// than the previous one
if (Math.Abs((presum - diff) - k) < mini) {
// update the minimal difference
mini = Math.Abs((presum - diff) - k);
// update the sum
sum = presum - diff;
}
// also check for the one before that
// since the sum can be greater than
// or less than K also
it--;
// get the prefix sum till start
// of the subarray
diff = it;
// if the subarray sum is closest to K
// than the previous one
if (Math.Abs((presum - diff) - k) < mini) {
// update the minimal difference
mini = Math.Abs((presum - diff) - k);
// update the sum
sum = presum - diff;
}
}
// if there exists no such prefix sum
// then the current prefix sum is
// checked and updated
else {
// if the subarray sum is closest to K
// than the previous one
if (Math.Abs(presum - k) < mini) {
// update the minimal difference
mini = Math.Abs(presum - k);
// update the sum
sum = presum + 1;
}
}
// insert the current prefix sum
s.Add(presum);
}
return sum-1;
}
public static int lower_bound(SortedSet<int> s, int val)
{
List<int> temp = new List<int>();
temp.AddRange(s);
temp.Sort();
temp.Reverse();
if (temp.IndexOf(val) + 1 == temp.Count)
return -1;
return temp[temp.IndexOf(val) + 1];
}
// Driver Code
public static void Main(String[] args) {
int []a = { -5, 12, -3, 4, -15, 6, 1 };
int n = a.Length;
int k = 2;
Console.Write(closestSubarraySumToK(a, n, k));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// javascript program to find the
// sum of subarray whose sum is
// closest to K
// Function to find the sum of subarray
// whose sum is closest to K
function closestSubarraySumToK(a , n , k) {
// Declare a set
var s = [];
// initially consider the
// first subarray as the first
// element in the array
var presum = a[0];
// insert
s.push(a[0]);
// Initially let this difference
// be the minimum
var mini = Math.abs(a[0] - k);
// let this be the sum
// of the subarray
// to be searched initially
var sum = presum;
// iterate for all the array elements
for (var i = 1; i < n; i++) {
s.sort();
// calculate the prefix sum
presum += a[i];
// find the closest subarray
// sum to by using lower_bound
var it = lower_bound(s,presum - k);
if(it == -1)
continue;
// if it is the first element
// in the set
if (it == s[0]) {
// get the prefix sum till start
// of the subarray
var diff = it;
// if the subarray sum is closest to K
// than the previous one
if (Math.abs((presum - diff) - k) < mini) {
// update the minimal difference
mini = Math.abs((presum - diff) - k);
// update the sum
sum = presum - diff;
}
}
// if the difference is
// present in between
else if (it == s[s.length-1]) {
// get the prefix sum till start
// of the subarray
var diff = it;
// if the subarray sum is closest to K
// than the previous one
if (Math.abs((presum - diff) - k) < mini) {
// update the minimal difference
mini = Math.abs((presum - diff) - k);
// update the sum
sum = presum - diff;
}
// also check for the one before that
// since the sum can be greater than
// or less than K also
it--;
// get the prefix sum till start
// of the subarray
diff = it;
// if the subarray sum is closest to K
// than the previous one
if (Math.abs((presum - diff) - k) < mini) {
// update the minimal difference
mini = Math.abs((presum - diff) - k);
// update the sum
sum = presum - diff;
}
}
// if there exists no such prefix sum
// then the current prefix sum is
// checked and updated
else {
// if the subarray sum is closest to K
// than the previous one
if (Math.abs(presum - k) < mini) {
// update the minimal difference
mini = Math.abs(presum - k);
// update the sum
sum = presum + 1;
}
}
// insert the current prefix sum
s.push(presum);
}
return sum;
}
function lower_bound(s, val) {
let temp = [...s];
temp.sort((a, b) => a - b);
return temp[temp.indexOf(val) + 1];
}
// Driver Code
var a = [ -5, 12, -3, 4, -15, 6, 1 ];
var n = a.length;
var k = 2;
document.write(closestSubarraySumToK(a, n, k));
// This code is contributed by Rajput-Ji
</script>
Producción
1
Complejidad de tiempo: O (N log N), donde N representa el tamaño de la array dada.
Espacio auxiliar: O(N), donde N representa el tamaño de la array dada.