Encontrar un subarreglo con una suma determinada es un problema común que aparece a menudo en entrevistas de codificación y programación competitiva. Este problema se puede resolver utilizando varias técnicas, cada una con sus propias compensaciones con respecto a la complejidad del tiempo y la complejidad del espacio. En este artículo, exploraremos múltiples enfoques para resolver el problema de encontrar un subarreglo con una suma determinada en Java.

Declaración del problema

Dada una matriz de números enteros y una suma objetivo, encuentre una submatriz continua en la matriz que sume la suma dada. El problema se puede dividir en dos variantes principales:

1. Submatriz con números positivos: la matriz contiene solo números positivos.
2. Submatriz con números mixtos: la matriz contiene números positivos y negativos.

Exploremos diferentes métodos para resolver estas variantes.

Enfoque 1: uso de la fuerza bruta

El enfoque de fuerza bruta implica verificar todos los subarreglos posibles y calcular sus sumas para ver si alguno de ellos es igual a la suma objetivo. Este enfoque funciona para ambas variantes, pero es ineficaz para matrices grandes debido a su complejidad de tiempo cuadrático.

Implementación

public class SubarraySumBruteForce {
  public static int[] findSubarrayWithGivenSum(int[] arr, int targetSum) {
    int n = arr.length;
    for (int start = 0; start 
Producción
Subarray found from index 1 to 3

Análisis

• Complejidad del tiempo: O(n²) debido a los dos bucles anidados que se iteran a través de la matriz.
• Complejidad del espacio: O(1) ya que no se utiliza espacio adicional más allá de la matriz de entrada.

Enfoque 2: uso de la ventana deslizante

El enfoque de ventana deslizante es eficiente para matrices que contienen solo números positivos. Esta técnica implica mantener una ventana de elementos que suman la suma objetivo. La ventana se expande agregando elementos hasta que la suma excede el objetivo y se contrae eliminando elementos desde el principio hasta que la suma es menor o igual al objetivo.

Implementación

public class SubarraySumSlidingWindow {
  public static int[] findSubarrayWithGivenSum(int[] arr, int targetSum) {
    int start = 0;
    int currentSum = 0;

    for (int end = 0; end  targetSum && start 
Producción
Subarray found from index 1 to 3

Análisis

• Complejidad del tiempo: O(n) ya que cada elemento se procesa como máximo dos veces.
• Complejidad del espacio: O(1) ya que no se necesita espacio adicional.