Subarreglo más pequeño con suma K de un arreglo

Dado un arreglo arr[] que consta de N enteros, la tarea es encontrar la longitud del subarreglo más pequeño con una suma igual a K .

Ejemplos:

Entrada: arr[] = {2, 4, 6, 10, 2, 1}, K = 12 
Salida: 2 
Explicación:  Todos los subarreglos posibles con suma 12 son {2, 4, 6} y {10, 2}.

Entrada: arr[] = {-8, -8, -3, 8}, K = 5 
Salida: 2

Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los subarreglos posibles y, para cada subarreglo, verificar si su suma es igual a K o no. Imprime la longitud mínima de todos esos subarreglos. 

Complejidad del tiempo:O(N ² )
Espacio Auxiliar:O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar aún más utilizando la técnica Prefix Sum y Map . 

Siga los pasos a continuación para resolver el problema:

• currPrefixSum almacenará la suma del prefijo que termina en i-ésimo índice.
• Itere sobre la array y siga calculando currPrefixSum .
  • Compruebe si currPrefixSum es igual a K.
    • En caso afirmativo, utilice esta longitud de subarreglo (currPrefixSum) para minimizar el resultado.
  • Además, verifique si la suma del prefijo requerido (currPrefixSum – K) se ha calculado previamente o no.
    • Si la suma del prefijo requerido se calculó previamente, busque la última aparición de esa suma del prefijo y utilícela para calcular la longitud de la suma del prefijo actual igual a K por (índice actual: última aparición de la suma del prefijo requerido) y utilícela para minimizar la resultado.
  • Almacene el currPrefixSum que termina en i-ésimo índice en el mapa.
• Finalmente, devuelve el resultado .
   

A continuación se muestra la implementación del enfoque anterior:

// c++ code to implement the above idea
#include <bits/stdc++.h>
using namespace std;
 
 
 
// Function to find the Smallest Subarray with
// Sum K from an Array
int smallestSubarraySumK(vector<int> & arr, int k ){
 
    // Use map here to store the prefixSum ending
    // at ith index.
    unordered_map<long long, int> unmap;
    int n = arr.size();
 
    // Store the current Prefix sum till ith index;
    long long currPrefixSum = 0;
 
    // Store the minimum size subarray whose sum is K
    long long result = INT_MAX;
 
    for(int i = 0; i < n; i++){
        currPrefixSum += arr[i];
 
        // Check if the current prefix sum is equals to K
        if(currPrefixSum == k){
            long long currLen = i + 1;
            result = min(result, currLen);
        }
 
        // Required PrefixSum
        long long requirePrefixSum
            = currPrefixSum - k;
 
        // Check if there exist any required
        // Prefix Sum or not
        if(unmap.count(requirePrefixSum)){
            long long foundIdx =
                unmap[requirePrefixSum];
            long long currIdx = i;
 
            result = min(result,
                           currIdx - foundIdx);
        }
 
        // Store the current prefix sum ending
        // at i
        unmap[currPrefixSum] = i;
    }
 
    if(result >= INT_MAX) return -1;
    // return the result
    return result;
}
 
  
// Driver code
int main(){
     
    vector<int> arr = {-8, -8, -3, 8};
    int k = 5;
 
    cout << smallestSubarraySumK(arr, k);
    return 0;
}

// Java Program to implement
// the above approach
import java.util.*;
public class Main {
 
// Function to find the Smallest Subarray with Sum
// K from an Array
static int smallestSubarraySumK(int arr[], int n, int K)
{
    // Use map here to store the prefixSum ending
    // at ith index.
    HashMap<Integer,
    Integer> mp = new HashMap<Integer,
    Integer>();
 
    // Store the current Prefix sum till ith
    // index;
    int currPrefixSum = 0;
 
    // Store the minimum size subarray whose
    // sum is K
    int result = Integer.MAX_VALUE;
 
    for(int i = 0; i < n; i++){
        currPrefixSum += arr[i];
 
        // Check if the current prefix sum is
        // equals to K
        if(currPrefixSum == K){
            int currLen = i + 1;
            result = Math.min(result, currLen);
        }
 
        // Required PrefixSum
        int requirePrefixSum = currPrefixSum - K;
 
        // Check if there exist any required Prefix Sum or not
        if(mp.containsKey(requirePrefixSum)){
            int foundIdx = mp.get(requirePrefixSum);
            int currIdx = i;
 
            result = Math.min(result, currIdx
                                - foundIdx);
        }
        
        // Store the current prefix sum ending at i
        mp.put(currPrefixSum, i);
    }
 
    if(result >= Integer.MAX_VALUE) return -1;
     
    // return the result
    return result;
}
 
// Driver Code
public static void main(String[] args){
 
    int arr[] = {-8, -8, -3, 8};
    int n = arr.length;
    int K = 5;
 
    System.out.println(smallestSubarraySumK(arr,
                                              n, K));
    
    }
}

# Python3 program to implement
# the above approach
from collections import defaultdict
import sys
 
# Function to find the length of the
# smallest subarray with sum K
def subArraylen(arr, n, K):
   
  mp = defaultdict(lambda : 0)
  currPrefixSum = 0
  result = sys.maxsize
  for i in range(n):
    currPrefixSum += arr[i]
    if(currPrefixSum == K):
      currLen = i + 1
      result = min(result, currLen)
    requirePrefixSum = currPrefixSum - K
       
    if(requirePrefixSum in mp.keys()):
      foundIdx = mp[requirePrefixSum]
      currIdx = i
      result = min(result, currIdx - foundIdx)
     
    mp[currPrefixSum] = i
  return result
      
     
# Driver Code
if __name__ == "__main__":
  arr = [-8, -8, -3, 8]
  n = len(arr)
   
  K = 5
 
  ln = subArraylen(arr, n, K)
 
  # Function call
  if(ln == sys.maxsize):
      print("-1")
  else:
      print(ln)
 
# This code is contributed by Shivam Singh

<script>
 
// JavaScript code to implement the above idea
 
// Function to find the Smallest Subarray with
// Sum K from an Array
function smallestSubarraySumK(arr,k)
{
 
    // Use map here to store the prefixSum ending
    // at ith index.
    let unmap = new Map();
    let n = arr.length
 
    // Store the current Prefix sum till ith index;
    let currPrefixSum = 0;
 
    // Store the minimum size subarray whose sum is K
    let result = Number.MAX_VALUE;
 
    for(let i = 0; i < n; i++)
    {
        currPrefixSum += arr[i];
 
        // Check if the current prefix sum is equals to K
        if(currPrefixSum == k){
            let currLen = i + 1;
            result = Math.min(result, currLen);
        }
 
        // Required PrefixSum
        let requirePrefixSum
            = currPrefixSum - k;
 
        // Check if there exist any required
        // Prefix Sum or not
        if(unmap.has(requirePrefixSum)){
            let foundIdx =
                unmap.get(requirePrefixSum);
            let currIdx = i;
 
            result = Math.min(result,
                           currIdx - foundIdx);
        }
 
        // Store the current prefix sum ending
        // at i
        unmap.set(currPrefixSum, i);
    }
 
    if(result >= Number.MAX_VALUE) return -1;
     
    // return the result
    return result;
}
 
// Driver code
let arr = [-8, -8, -3, 8];
let k = 5;
 
document.write(smallestSubarraySumK(arr, k));
 
// This code is contributed by shinjanpatra
 
</script>

2

Complejidad del tiempo:O(N)
Espacio Auxiliar:EN)