Dada una matriz de n enteros positivos y un entero positivo s, encuentre la longitud mínima de una submatriz cuya suma ≥ s. Si no hay uno, devuelve 0 en su lugar.
Por ejemplo, dada la matriz [2,3,1,2,4,3] y s = 7, el subarreglo [4,3] tiene la longitud mínima de 2 bajo la restricción del problema.
Análisis
Podemos usar 2 puntos para marcar los límites izquierdo y derecho de la ventana deslizante. Cuando la suma sea mayor que el objetivo, mueva el puntero izquierdo; cuando la suma sea menor que el objetivo, mueva el puntero derecho.
Solución Java: dos punteros
Una sencilla solución para ventanas correderas.
public int minSubArrayLen(int s, int[] nums) { if(nums==null || nums.length==1) return 0; int result = nums.length; int start=0; int sum=0; int i=0; boolean exists = false; while(i<=nums.length){ if(sum>=s){ exists=true; //mark if there exists such a subarray if(start==i-1){ return 1; } result = Math.min(result, i-start); sum=sum-nums[start]; start++; }else{ if(i==nums.length) break; sum = sum+nums[i]; i++; } } if(exists) return result; else return 0; } |
Del mismo modo, también podemos escribirlo de una manera más legible.
public int minSubArrayLen(int s, int[] nums) { if(nums==null||nums.length==0) return 0; int i=0; int j=0; int sum=0; int minLen = Integer.MAX_VALUE; while(j<nums.length){ if(sum<s){ sum += nums[j]; j++; }else{ minLen = Math.min(minLen, j-i); if(i==j-1) return 1; sum -=nums[i]; i++; } } while(sum>=s){ minLen = Math.min(minLen, j-i); sum -=nums[i++]; } return minLen==Integer.MAX_VALUE? 0: minLen; } |
