Dado un arreglo A[] que consta de N enteros y un entero K , la tarea es encontrar la longitud del subarreglo más pequeño con una suma mayor o igual que K . Si no existe tal subarreglo, imprima -1 .
Ejemplos:
Entrada: A[] = {2, -1, 2}, K = 3
Salida: 3
Explicación:
La suma del arreglo dado es 3.
Por lo tanto, el subarreglo más pequeño posible que satisface la condición requerida es el arreglo completo.
Por lo tanto, la longitud es 3.Entrada: A[] = {2, 1, 1, -4, 3, 1, -1, 2}, K = 5
Salida: 4
Enfoque ingenuo:
el enfoque más simple para resolver el problema es generar todos los subarreglos posibles del arreglo dado y verificar qué suma de subarreglo es mayor o igual a K . Entre todos esos subarreglos que satisfacen la condición, imprima el subarreglo que tenga la longitud mínima.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente:
el enfoque anterior se puede optimizar aún más utilizando la array de suma de prefijos y la búsqueda binaria . Siga los pasos a continuación:
- Inicialice una array para almacenar la suma de prefijos de la array original.
- Hash la array de suma de prefijos con los índices usando un Map .
- Si ya se encuentra una suma mayor con un índice menor , entonces no tiene sentido hacer hash de una suma de prefijo que sea menor que la suma de prefijo más grande obtenida hasta ahora. Por lo tanto, hash el orden creciente de la suma del prefijo.
- Recorriendo la array y si algún elemento es mayor o igual a K , devuelve 1 como respuesta.
- De lo contrario, para cada elemento, realice una búsqueda binaria sobre los índices (i, n-1) en la array de suma de prefijos para encontrar el primer índice con una suma de al menos K .
- Devuelve el subarreglo de longitud mínima obtenido de los pasos anteriores.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to perform Binary Search
// and return the smallest index with
// sum greater than value
int binary_search(map<int, vector<int> >& m,
int value, int index)
{
// Search the value in map
auto it = m.lower_bound(value);
// If all keys in the map
// are less then value
if (it == m.end())
return 0;
// Check if the sum is found
// at a greater index
auto it1
= lower_bound(it->second.begin(),
it->second.end(), index);
if ((it1 - it->second.begin())
!= it->second.size())
return *it1;
return 0;
}
// Function to find the smallest subarray
// with sum greater than equal to K
int findSubarray(int arr[], int n, int k)
{
// Prefix sum array
int pre_array[n];
// Stores the hashes to prefix sum
map<int, vector<int> > m;
pre_array[0] = arr[0];
m[pre_array[0]].push_back(0);
// If any array element is
// greater than equal to k
if (arr[0] >= k)
return 1;
int ans = INT_MAX;
for (int i = 1; i < n; i++) {
pre_array[i]
= arr[i] + pre_array[i - 1];
// If prefix sum exceeds K
if (pre_array[i] >= k)
// Update size of subarray
ans = min(ans, i + 1);
auto it = m.rbegin();
// Hash prefix sum in
// increasing order
if (pre_array[i] >= it->first)
m[pre_array[i]].push_back(i);
}
for (int i = 1; i < n; i++) {
int temp
= binary_search(m,
pre_array[i - 1] + k,
i);
if (temp == 0)
continue;
// Update size of subarray
ans = min(ans, temp - i + 1);
}
// If any subarray is found
if (ans <= n)
return ans;
// If no such subarray exists
return -1;
}
// Driver Code
int main()
{
int arr[] = { 2, 1, 1, -4, 3, 1, -1, 2 };
int k = 5;
int n = sizeof(arr) / sizeof(arr[0]);
cout << findSubarray(arr, n, k) << endl;
return 0;
}
4
Complejidad temporal: O(NlogN)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por godaraji47 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA