Encuentre un subarray que tenga la suma dada en un arreglo de enteros
Dada una matriz de enteros, encuentre una subarray que tenga una suma dada en él.
Por ejemplo,
Input: nums[] = {2, 6, 0, 9, 7, 3, 1, 4, 1, 10}, target = 15
Output: {6, 0, 9}
Input: nums[] = {0, 5, -7, 1, -4, 7, 6, 1, 4, 1, 10}, target = 15
Output: {1, -4, 7, 6, 1, 4} or {4, 1, 10}
Input: nums[] = {0, 5, -7, 1, -4, 7, 6, 1, 4, 1, 10}, target = -3
Output: {1, -4} or {-7, 1, -4, 7}
Output: {6, 0, 9}
Input: nums[] = {0, 5, -7, 1, -4, 7, 6, 1, 4, 1, 10}, target = 15
Output: {1, -4, 7, 6, 1, 4} or {4, 1, 10}
Input: nums[] = {0, 5, -7, 1, -4, 7, 6, 1, 4, 1, 10}, target = -3
Output: {1, -4} or {-7, 1, -4, 7}
1. Uso de la ventana deslizante
Podemos resolver este problema usando un ventana deslizante. La idea es mantener una ventana que comience desde el elemento actual, y la suma de sus elementos sea mayor o igual a la suma dada. Si la suma de la ventana actual se vuelve menor que la suma dada, entonces la ventana es inestable y seguimos agregando elementos a la ventana actual desde su derecha hasta que la ventana vuelve a ser estable. Imprime la ventana si su suma es igual a la suma dada en cualquier punto. Tenga en cuenta que este enfoque solo funcionará con una array de enteros positivos.
El algoritmo se puede implementar de la siguiente manera en C++, Java y Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include <stdio.h> // Función para imprimir un subarray que tiene una suma dada usando // técnica de ventana corrediza void findSubarray(int nums[], int n, int target) { // mantiene la suma de la ventana actual int windowSum = 0; // mantener una ventana [low, high-1] int low = 0, high = 0; // considera cada subarray a partir del índice `low` for (low = 0; low < n; low++) { // si la suma de la ventana actual es menor que la suma dada, // luego agrega elementos a la ventana actual desde la derecha while (windowSum < target && high < n) { windowSum += nums[high]; high++; } // si la suma de la ventana actual es igual a la suma dada if (windowSum == target) { printf("Subarray found [%d–%d]\n", low, high - 1); return; } // En este punto, la suma de la ventana actual es mayor que la suma dada. // Eliminar el elemento actual (elemento más a la izquierda) de la ventana windowSum -= nums[low]; } } int main(void) { // una array de enteros positivos int nums[] = { 2, 6, 0, 9, 7, 3, 1, 4, 1, 10 }; int target = 15; int n = sizeof(nums)/sizeof(nums[0]); findSubarray(nums, n, target); return 0; } |
Resultado:
Subarray found [1–3]
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
class Main { // Función para imprimir un subarray que tiene una suma dada usando // técnica de ventana corrediza public static void findSubarray(int[] nums, int target) { // mantiene la suma de la ventana actual int windowSum = 0; // mantener una ventana [low, high-1] int high = 0; // considera cada subarray a partir del índice `low` for (int low = 0; low < nums.length; low++) { // si la suma de la ventana actual es menor que la suma dada, // luego agrega elementos a la ventana actual desde la derecha while (windowSum < target && high < nums.length) { windowSum += nums[high]; high++; } // si la suma de la ventana actual es igual a la suma dada if (windowSum == target) { System.out.printf("Subarray found [%d–%d]", low, high - 1); return; } // En este punto, la suma de la ventana actual es mayor que la suma dada. // Eliminar el elemento actual (elemento más a la izquierda) de la ventana windowSum -= nums[low]; } } public static void main(String[] args) { // una array de enteros positivos int[] nums = { 2, 6, 0, 9, 7, 3, 1, 4, 1, 10 }; int target = 15; findSubarray(nums, target); } } |
Resultado:
Subarray found [1–3]
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
# Función para imprimir una sublista que tiene una suma dada usando # Técnica de ventana corredera def findSublist(nums, target): # mantiene la suma de la ventana actual windowSum = 0 # mantener una ventana [low, high-1] (low, high) = (0, 0) # considera cada sublista a partir del índice `low` for low in range(len(nums)): # si la suma de la ventana actual es menor que la suma dada, # luego agregue elementos a la ventana actual desde la derecha while windowSum < target and high < len(nums): windowSum += nums[high] high = high + 1 # si la suma de la ventana actual es igual a la suma dada if windowSum == target: print('Sublist found', (low, high - 1)) return # En este punto, la suma de la ventana actual es mayor que la suma dada. # Eliminar el elemento actual (elemento más a la izquierda) de la ventana windowSum -= nums[low] if __name__ == '__main__': # una lista de enteros positivos nums = [2, 6, 0, 9, 7, 3, 1, 4, 1, 10] target = 15 findSublist(nums, target) |
Resultado:
Sublist found (1, 3)
La complejidad temporal de la solución anterior es O(n) y no requiere ningún espacio adicional, donde n es el tamaño de la entrada.
2. Uso de hashing
La solución anterior fallará para números negativos. Nosotros podemos usar hash para verificar si un subarray con la suma dada existe en el arreglo o no. La idea es atravesar la matriz dada y mantener la suma de los elementos vistos hasta ahora. Si la diferencia entre la suma actual y la suma dada se ve antes (es decir, la diferencia existe en el conjunto), devuelve verdadero ya que hay al menos un subarray con la suma dada que termina en el índice actual; de lo contrario, inserte la suma en el conjunto.
A continuación se muestra la implementación del algoritmo anterior en C++, Java y Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include <iostream> #include <unordered_set> using namespace std; // Función para verificar si existe un subarray con la suma dada en // la array o no bool findSubarray(int nums[], int n, int target) { // crea un conjunto vacio unordered_set<int> set; // inserta el número 0 en el conjunto para manejar el caso cuando un // el subarray con la suma dada comienza desde el índice 0 set.insert(0); // realizar un seguimiento de la suma de elementos hasta el momento int sum_so_far = 0; // recorrer la array dada for (int i = 0; i < n; i++) { // actualizar `sum_so_far` sum_so_far += nums[i]; // si `sum_so_far - target` se ve antes, hemos encontrado // el subarray con suma igual a `target` if (set.find(sum_so_far - target) != set.end()) { return true; } // de lo contrario, suma la suma de los elementos hasta ahora en el conjunto set.insert(sum_so_far); } // llegamos aquí cuando no existe un subarray return false; } int main() { // una array de enteros int nums[] = { 0, 5, -7, 1, -4, 7, 6, 1, 4, 1, 10 }; int target = -3; int n = sizeof(nums)/sizeof(nums[0]); if (findSubarray(nums, n, target)) { cout << "Subarray with the given sum exists"; } else { cout << "Subarray with the given sum does not exist"; } return 0; } |
Resultado:
Subarray with the given sum exists
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
import java.util.HashSet; import java.util.Set; class Main { // Función para verificar si existe un subarray con la suma dada en // la array o no public static boolean findSubarray(int[] nums, int target) { // crea un conjunto vacio Set<Integer> set = new HashSet<>(); // inserta el número 0 en el conjunto para manejar el caso cuando un // el subarray con la suma dada comienza desde el índice 0 set.add(0); // realizar un seguimiento de la suma de elementos hasta el momento int sum_so_far = 0; // recorrer la array dada for (int i: nums) { // actualizar `sum_so_far` sum_so_far += i; // si `sum_so_far - target` se ve antes, hemos encontrado // el subarray con suma igual a `target` if (set.contains(sum_so_far - target)) { return true; } // de lo contrario, suma la suma de los elementos hasta ahora en el conjunto set.add(sum_so_far); } // llegamos aquí cuando no existe un subarray return false; } public static void main(String[] args) { // una array de enteros int[] nums = { 0, 5, -7, 1, -4, 7, 6, 1, 4, 1, 10 }; int target = -3; if (findSubarray(nums, target)) { System.out.println("Subarray with the given sum exists"); } else { System.out.println("Subarray with the given sum does not exist"); } } } |
Resultado:
Subarray with the given sum exists
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
# Función para verificar si una sublista con la suma dada existe en la lista o no def findSublist(nums, target): # crear un conjunto vacío s = set() # inserte el número 0 en el conjunto para manejar el caso cuando un # La sublista # con la suma dada comienza desde el índice 0 s.add(0) # realiza un seguimiento de la suma de elementos hasta el momento sum_so_far = 0 # recorrer la lista dada for i in nums: # Actualización # sum_so_far sum_so_far += i # si `sum_so_far - target` se ve antes, hemos encontrado # la sublista con suma igual a `target` if (sum_so_far - target) in s: return True # de lo contrario, suma la suma de los elementos hasta ahora en el conjunto s.add(sum_so_far) # llegamos aquí cuando no existe una sublista return False if __name__ == '__main__': # una lista de enteros nums = [0, 5, -7, 1, -4, 7, 6, 1, 4, 1, 10] target = -3 if findSublist(nums, target): print('Sublist with the given sum exists') else: print('Sublist with the given sum does not exist') |
Resultado:
Sublist with the given sum exists
También podemos imprimir el subarray usando hashing. La idea es usar un mapa en lugar de un conjunto que almacene el índice final del subarray y su suma.
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include <iostream> #include <unordered_map> using namespace std; // Función para imprimir un subarray que tiene una suma dada usando hashing void findSubarray(int nums[], int n, int target) { // crea un mapa vacio unordered_map<int, int> map; // inserta (0, -1) par en el conjunto para manejar el caso cuando un // el subarray con la suma dada comienza desde el índice 0 map.insert(pair<int, int>(0, -1)); // realizar un seguimiento de la suma de elementos hasta el momento int sum_so_far = 0; // recorrer la array dada for (int i = 0; i < n; i++) { // actualizar `sum_so_far` sum_so_far += nums[i]; // si `sum_so_far - target` se ve antes, hemos encontrado // el subarray con suma igual a `target` if (map.find(sum_so_far - target) != map.end()) { cout << "Subarray found [" << map[sum_so_far - target] + 1 << "–" << i << "]" << endl; return; } // insertar (suma actual, índice actual) par en el mapa map.insert(pair<int, int>(sum_so_far, i)); } } int main() { // una array de enteros int nums[] = { 0, 5, -7, 1, -4, 7, 6, 1, 4, 1, 10 }; int target = 15; int n = sizeof(nums)/sizeof(nums[0]); findSubarray(nums, n, target); return 0; } |
Resultado:
Subarray found [3–8]
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
import java.util.HashMap; import java.util.Map; class Main { // Función para imprimir un subarray que tiene una suma dada usando hashing public static void findSubarray(int[] nums, int target) { // crea un mapa vacio Map<Integer, Integer> map = new HashMap<>(); // inserta (0, -1) par en el conjunto para manejar el caso cuando un // el subarray con la suma dada comienza desde el índice 0 map.put(0, -1); // realizar un seguimiento de la suma de elementos hasta el momento int sum_so_far = 0; // recorrer la array dada for (int i = 0; i < nums.length; i++) { // actualizar `sum_so_far` sum_so_far += nums[i]; // si `sum_so_far - target` se ve antes, hemos encontrado // el subarray con suma igual a `target` if (map.containsKey(sum_so_far - target)) { System.out.println("Subarray found [" + (map.get(sum_so_far - target) + 1) + "–" + i + "]"); return; } // insertar (suma actual, índice actual) par en el mapa map.put(sum_so_far, i); } } public static void main(String[] args) { // una array de enteros int[] nums = { 0, 5, -7, 1, -4, 7, 6, 1, 4, 1, 10 }; int target = 15; findSubarray(nums, target); } } |
Resultado:
Subarray found [3–8]
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
# Función para imprimir una sublista que tiene una suma dada usando hashing def findSublist(nums, target): # inserte (0, -1) par en el conjunto para manejar el caso cuando un # La sublista # con la suma dada comienza desde el índice 0 d = {0: -1} # realiza un seguimiento de la suma de elementos hasta el momento sum_so_far = 0 # recorrer la lista dada for i in range(len(nums)): # Actualización # sum_so_far sum_so_far += nums[i] # si `sum_so_far - target` se ve antes, hemos encontrado # la sublista con suma igual a `target` if (sum_so_far - target) in d: print('Sublist found', (d.get(sum_so_far - target) + 1, i)) return # insertar (suma actual, índice actual) par en el diccionario d[sum_so_far] = i if __name__ == '__main__': # una lista de enteros nums = [0, 5, -7, 1, -4, 7, 6, 1, 4, 1, 10] target = 15 findSublist(nums, target) |
Resultado:
Sublist found (3, 8)
La complejidad temporal de la solución anterior es O(n) y requiere O(n) espacio adicional, donde n es el tamaño de la entrada.