Dada una array desordenada de enteros, encuentre una subarreglo que se sume a un número dado. Si hay más de un subarreglo con la suma del número dado, imprima cualquiera de ellos.
Ejemplos :
Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33
Output: Sum found between indexes 2 and 4
Input: arr[] = {10, 2, -2, -20, 10}, sum = -10
Output: Sum found between indexes 0 to 3
Input: arr[] = {-10, 0, 2, -2, -20, 10}, sum = 20
Output: No subarray with given sum exists.
Ya habíamos discutido un enfoque para encontrar un subarreglo con una suma dada en un arreglo que contiene elementos tanto positivos como negativos usando Hashing
. En este artículo, se discute un enfoque sin usar ningún espacio adicional.
La idea es modificar la array para que contenga solo elementos positivos:
- Encuentre el elemento negativo más pequeño de la array y aumente cada valor de la array por el valor absoluto del elemento negativo más pequeño encontrado.
Podemos notar que después de hacer la modificación anterior, la suma de cada subarreglo también aumentará en:
(number of elements in the subarray) * (absolute value of min element)
Después de realizar la modificación anterior en la array de entrada, la tarea se reduce a encontrar si hay algún subarreglo en la array dada de solo números positivos con la nueva suma objetivo . Esto se puede hacer usando la técnica de ventana deslizante en tiempo O(N) y espacio constante.
Cada vez que agregue elementos a la ventana, incremente la suma objetivo por el valor absoluto del elemento mínimo y, de manera similar, mientras elimina elementos de la ventana actual, disminuya la suma objetivo por el valor absoluto del elemento mínimo para que para cada subarreglo de longitud, digamos K, la suma objetivo actualizada será:
targetSum = sum + K*abs(minimum element)
A continuación se muestra el enfoque para el mismo:
- Inicialice una variable curr_sum como primer elemento.
- La variable curr_sum indica la suma del subarreglo actual.
- Comience desde el segundo elemento y agregue todos los elementos uno por uno a curr_sum, y siga incrementando la suma objetivo por abs (elemento mínimo).
- Si curr_sum se vuelve igual a la suma objetivo, imprima la solución.
- Si curr_sum excede la suma, elimine los elementos finales mientras disminuye curr_sum es mayor que la suma y siga disminuyendo la suma objetivo por abs (elemento mínimo).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to check if subarray with sum
// exists when negative elements are also present
#include <bits/stdc++.h>
using namespace std;
// Function to check if subarray with sum
// exists when negative elements are also present
void subArraySum(int arr[], int n, int sum)
{
int minEle = INT_MAX;
// Find minimum element in the array
for (int i = 0; i < n; i++)
minEle = min(arr[i], minEle);
// Initialize curr_sum as value of first element
// and starting point as 0
int curr_sum = arr[0] + abs(minEle), start = 0, i;
// Starting window length will be 1,
// For generating new target sum,
// add abs(minEle) to sum only 1 time
int targetSum = sum;
// Add elements one by one to curr_sum
// and if the curr_sum exceeds the
// updated sum, then remove starting element
for (i = 1; i <= n; i++) {
// If curr_sum exceeds the sum,
// then remove the starting elements
while (curr_sum - (i - start) * abs(minEle) > targetSum && start < i) {
curr_sum = curr_sum - arr[start] - abs(minEle);
start++;
}
// If curr_sum becomes equal to sum, then return true
if (curr_sum - (i - start) * abs(minEle) == targetSum) {
cout << "Sum found between indexes " << start << " and " << i - 1;
return;
}
// Add this element to curr_sum
if (i < n) {
curr_sum = curr_sum + arr[i] + abs(minEle);
}
}
// If we reach here, then no subarray
cout << "No subarray found";
}
// Driver Code
int main()
{
int arr[] = { 10, -12, 2, -2, -20, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
int sum = -10;
subArraySum(arr, n, sum);
return 0;
}
Java
// Java program to check if subarray with sum
// exists when negative elements are also present
class GFG
{
// Function to check if subarray with sum
// exists when negative elements are also present
static void subArraySum(int arr[], int n, int sum)
{
int minEle = Integer.MAX_VALUE;
// Find minimum element in the array
for (int i = 0; i < n; i++)
minEle = Math.min(arr[i], minEle);
// Initialize curr_sum as value of
// first element and starting point as 0
int curr_sum = arr[0] + Math.abs(minEle);
int start = 0, i;
// Starting window length will be 1,
// For generating new target sum,
// add abs(minEle) to sum only 1 time
int targetSum = sum;
// Add elements one by one to curr_sum
// and if the curr_sum exceeds the
// updated sum, then remove starting element
for (i = 1; i <= n; i++)
{
// If curr_sum exceeds the sum,
// then remove the starting elements
while (curr_sum - (i - start) *
Math.abs(minEle) > targetSum &&
start < i)
{
curr_sum = curr_sum - arr[start] -
Math.abs(minEle);
start++;
}
// If curr_sum becomes equal to sum,
// then return true
if (curr_sum - (i - start) *
Math.abs(minEle) == targetSum)
{
System.out.println("Sum found between indexes " +
start + " and " + (i - 1));
return;
}
// Add this element to curr_sum
if (i < n)
{
curr_sum = curr_sum + arr[i] +
Math.abs(minEle);
}
}
// If we reach here, then no subarray
System.out.println("No subarray found");
}
// Driver Code
public static void main (String[] args)
{
int arr[] = { 10, -12, 2, -2, -20, 10 };
int n = arr.length;
int sum = -10;
subArraySum(arr, n, sum);
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 program to check if subarray with summ
# exists when negative elements are also present
# Function to check if subarray with summ
# exists when negative elements are also present
def subArraySum(arr, n, summ):
minEle = 10**9
# Find minimum element in the array
for i in range(n):
minEle = min(arr[i], minEle)
# Initialize curr_summ as value of
# first element and starting point as 0
curr_summ = arr[0] + abs(minEle)
start = 0
# Starting window length will be 1,
# For generating new target summ,
# add abs(minEle) to summ only 1 time
targetSum = summ
# Add elements one by one to curr_summ
# and if the curr_summ exceeds the
# updated summ, then remove starting element
for i in range(1, n + 1):
# If curr_summ exceeds the summ,
# then remove the starting elements
while (curr_summ - (i - start) * abs(minEle) >
targetSum and start < i):
curr_summ = curr_summ - arr[start] - abs(minEle)
start += 1
# If curr_summ becomes equal to summ,
# then return true
if (curr_summ - (i - start) *
abs(minEle) == targetSum):
print("Sum found between indexes",
start, "and", i - 1)
return
# Add this element to curr_summ
if (i < n):
curr_summ = curr_summ + arr[i] + abs(minEle)
# If we reach here, then no subarray
print("No subarray found")
# Driver Code
arr = [10, -12, 2, -2, -20, 10]
n = len(arr)
summ = -10
subArraySum(arr, n, summ)
# This code is contributed by Mohit Kumar
C#
// C# program to check if subarray
// with sum exists when negative
// elements are also present
using System;
class GFG
{
// Function to check if subarray
// with sum exists when negative
// elements are also present
static void subArraySum(int []arr,
int n, int sum)
{
int minEle = int.MaxValue;
int i;
// Find minimum element in the array
for (i = 0; i < n; i++)
minEle = Math.Min(arr[i], minEle);
// Initialize curr_sum as value of
// first element and starting point as 0
int curr_sum = arr[0] + Math.Abs(minEle);
int start = 0;
// Starting window length will be 1,
// For generating new target sum,
// add abs(minEle) to sum only 1 time
int targetSum = sum;
// Add elements one by one to curr_sum
// and if the curr_sum exceeds the
// updated sum, then remove starting element
for (i = 1; i <= n; i++)
{
// If curr_sum exceeds the sum,
// then remove the starting elements
while (curr_sum - (i - start) *
Math.Abs(minEle) > targetSum &&
start < i)
{
curr_sum = curr_sum - arr[start] -
Math.Abs(minEle);
start++;
}
// If curr_sum becomes equal to sum,
// then return true
if (curr_sum - (i - start) *
Math.Abs(minEle) == targetSum)
{
Console.Write("Sum found between indexes " +
start + " and " + (i - 1));
return;
}
// Add this element to curr_sum
if (i < n)
{
curr_sum = curr_sum + arr[i] +
Math.Abs(minEle);
}
}
// If we reach here, then no subarray
Console.Write("No subarray found");
}
// Driver Code
static public void Main ()
{
int []arr = { 10, -12, 2, -2, -20, 10 };
int n = arr.Length;
int sum = -10;
subArraySum(arr, n, sum);
}
}
// This code is contributed by ajit
Javascript
<script>
// Java Script program to check if subarray with sum
// exists when negative elements are also present
// Function to check if subarray with sum
// exists when negative elements are also present
function subArraySum(arr,n,sum)
{
let minEle = Number.MAX_VALUE;
// Find minimum element in the array
for (let i = 0; i < n; i++)
minEle = Math.min(arr[i], minEle);
// Initialize curr_sum as value of
// first element and starting point as 0
let curr_sum = arr[0] + Math.abs(minEle);
let start = 0, i;
// Starting window length will be 1,
// For generating new target sum,
// add abs(minEle) to sum only 1 time
let targetSum = sum;
// Add elements one by one to curr_sum
// and if the curr_sum exceeds the
// updated sum, then remove starting element
for (i = 1; i <= n; i++)
{
// If curr_sum exceeds the sum,
// then remove the starting elements
while (curr_sum - (i - start) *
Math.abs(minEle) > targetSum &&
start < i)
{
curr_sum = curr_sum - arr[start] -
Math.abs(minEle);
start++;
}
// If curr_sum becomes equal to sum,
// then return true
if (curr_sum - (i - start) *
Math.abs(minEle) == targetSum)
{
document.write("Sum found between indexes " +
start + " and " + (i - 1));
return;
}
// Add this element to curr_sum
if (i < n)
{
curr_sum = curr_sum + arr[i] +
Math.abs(minEle);
}
}
// If we reach here, then no subarray
document.write("No subarray found");
}
// Driver Code
let arr = [ 10, -12, 2, -2, -20, 10 ];
let n = arr.length;
let sum = -10;
subArraySum(arr, n, sum);
// This code is contributed by sravan kumar
</script>
Producción:
Sum found between indexes 1 and 2
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA