Menor Subarray com Soma K de um Array
Dada uma array arr [] consistindo de N números inteiros, a tarefa é encontrar o comprimento da menor subarray com uma soma igual a K .
Exemplos:
Entrada: arr [] = {2, 4, 6, 10, 2, 1}, K = 12
Saída: 2
Explicação:
Todos os subarrayes possíveis com soma 12 são {2, 4, 6} e {10, 2}.Entrada: arr [] = {1, 2, 4, 3, 2, 4, 1}, K = 7
Saída: 2
Abordagem Ingênua: A abordagem mais simples para resolver o problema é gerar todos os subarrayes possíveis e para cada subarray verificar se sua soma é igual a K ou não. Imprima o comprimento mínimo de todos esses subarray.
Complexidade de tempo: O (N 2 )
Espaço auxiliar: O (1)
Abordagem eficiente: A abordagem acima pode ser otimizada ainda mais usando a técnica Prefix Sum e HashMap . Siga as etapas abaixo para resolver o problema:
- Calcule a soma do prefixo para cada índice e armazene (índice, soma do prefixo) como pares de valores-chave no mapa.
- Percorra a array de soma de prefixo e calcule a diferença entre a soma de prefixo e a soma necessária.
- Se o valor de diferença existir no HashMap, isso significa que existe um subarray com uma soma igual a K , então compare o comprimento do subarray com o comprimento mínimo obtido e atualize o comprimento mínimo de acordo.
Abaixo está a implementação da abordagem acima:
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the length of the
// smallest subarray with sum K
int subArraylen(int arr[], int n, int K)
{
// Stores the frequency of
// prefix sums in the array
unordered_map<int, int> mp;
mp[arr[0]] = 0;
for (int i = 1; i < n; i++) {
arr[i] = arr[i] + arr[i - 1];
mp[arr[i]] = i;
}
// Initialize len as INT_MAX
int len = INT_MAX;
for (int i = 0; i < n; i++) {
// If sum of array till i-th
// index is less than K
if (arr[i] < K)
// No possible subarray
// exists till i-th index
continue;
else {
// Find the exceeded value
int x = arr[i] - K;
// If exceeded value is zero
if (x == 0)
len = min(len, i);
if (mp.find(x) == mp.end())
continue;
else {
len = min(len, i - mp[x]);
}
}
}
return len;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 4, 3, 2, 4, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
int K = 7;
int len = subArraylen(arr, n, K);
if (len == INT_MAX) {
cout << "-1";
}
else {
cout << len << endl;
}
return 0;
}// Java Program to implement
// the above approach
import java.util.*;
class GFG{
// Function to find the length of the
// smallest subarray with sum K
static int subArraylen(int arr[], int n, int K)
{
// Stores the frequency of
// prefix sums in the array
HashMap<Integer,
Integer> mp = new HashMap<Integer,
Integer>();
mp.put(arr[0], 0);
for (int i = 1; i < n; i++)
{
arr[i] = arr[i] + arr[i - 1];
mp.put(arr[i], i);
}
// Initialize len as Integer.MAX_VALUE
int len = Integer.MAX_VALUE;
for (int i = 0; i < n; i++)
{
// If sum of array till i-th
// index is less than K
if (arr[i] < K)
// No possible subarray
// exists till i-th index
continue;
else
{
// Find the exceeded value
int x = K - arr[i];
// If exceeded value is zero
if (x == 0)
len = Math.min(len, i);
if (mp.containsValue(x))
continue;
else
{
len = Math.min(len, i );
}
}
}
return len;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 2, 4, 3, 2, 4, 1 };
int n = arr.length;
int K = 7;
int len = subArraylen(arr, n, K);
if (len == Integer.MAX_VALUE)
{
System.out.print("-1");
}
else
{
System.out.print(len + "\n");
}
}
}
// This code is contributed by Rohit_ranjan# 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):
# Stores the frequency of
# prefix sums in the array
mp = defaultdict(lambda : 0)
mp[arr[0]] = 0
for i in range(1, n):
arr[i] = arr[i] + arr[i - 1]
mp[arr[i]] = i
# Initialize ln
ln = sys.maxsize
for i in range(n):
# If sum of array till i-th
# index is less than K
if(arr[i] < K):
# No possible subarray
# exists till i-th index
continue
else:
# Find the exceeded value
x = K - arr[i]
# If exceeded value is zero
if(x == 0):
ln = min(ln, i)
if(x in mp.keys()):
continue
else:
ln = min(ln, i - mp[x])
return ln
# Driver Code
arr = [ 1, 2, 4, 3, 2, 4, 1 ]
n = len(arr)
K = 7
ln = subArraylen(arr, n, K)
# Function call
if(ln == sys.maxsize):
print("-1")
else:
print(ln)
# This code is contributed by Shivam Singh// C# Program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the length of the
// smallest subarray with sum K
static int subArraylen(int []arr, int n, int K)
{
// Stores the frequency of
// prefix sums in the array
Dictionary<int,
int> mp = new Dictionary<int,
int>();
mp.Add(arr[0], 0);
for (int i = 1; i < n; i++)
{
arr[i] = arr[i] + arr[i - 1];
mp.Add(arr[i], i);
}
// Initialize len as int.MaxValue
int len = int.MaxValue;
for (int i = 0; i < n; i++)
{
// If sum of array till i-th
// index is less than K
if (arr[i] < K)
// No possible subarray
// exists till i-th index
continue;
else
{
// Find the exceeded value
int x = K - arr[i];
// If exceeded value is zero
if (x == 0)
len = Math.Min(len, i);
if (mp.ContainsValue(x))
continue;
else
{
len = Math.Min(len, i );
}
}
}
return len;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 1, 2, 4, 3, 2, 4, 1 };
int n = arr.Length;
int K = 7;
int len = subArraylen(arr, n, K);
if (len == int.MaxValue)
{
Console.Write("-1");
}
else
{
Console.Write(len + "\n");
}
}
}
// This code is contributed by Rohit_ranjan<script>
// JavaScript Program to implement
// the above approach
// Function to find the length of the
// smallest subarray with sum K
function subArraylen(arr, n, K)
{
// Stores the frequency of
// prefix sums in the array
var mp = new Map();
mp.set(arr[0],0);
for (var i = 1; i < n; i++) {
arr[i] = arr[i] + arr[i - 1];
mp.set(arr[i],i);
}
// Initialize len as INT_MAX
var len = 10000000000;
for (var i = 0; i < n; i++) {
// If sum of array till i-th
// index is less than K
if (arr[i] < K)
// No possible subarray
// exists till i-th index
continue;
else {
// Find the exceeded value
var x = arr[i] - K;
// If exceeded value is zero
if (x == 0)
len = Math.min(len, i);
if (!mp.has(x))
continue;
else {
len = Math.min(len, i - mp.get(x));
}
}
}
return len;
}
// Driver Code
var arr = [1, 2, 4, 3, 2, 4, 1];
var n = arr.length;
var K = 7;
var len = subArraylen(arr, n, K);
if (len == 1000000000) {
document.write( "-1");
}
else {
document.write( len );
}
</script>Saída
2
Complexidade de tempo: O (NlogN)
Espaço auxiliar: O (N)
Outra abordagem eficiente:
A solução para o problema atual pode ser otimizada ainda mais usando a técnica de dois ponteiros . Funcionaria assim:
- Configure duas variáveis portadoras de índice - esquerda e direita , inicializadas com 0.
- Inicializa a soma atual com o valor do primeiro elemento, comprimento para INT_MAX e índice inicial para -1.
- Se a soma atual for menor que a soma exigida, incremente à direita e aumente a soma atual pelo valor do elemento no índice à direita .
- Se a soma atual for maior do que a soma necessária, diminua a soma atual pelo valor do elemento no índice esquerdo. Incremento à esquerda .
- Se a soma atual for igual à soma necessária, defina o comprimento com o mínimo de comprimento e direita - esquerda +1. Defina o índice inicial para l eft. Incrementar à direita .
- Quando os dois ponteiros apontam para o mesmo elemento, verifique se é a soma necessária. Se for esse o caso, siga a etapa 5. Se não, aumente para a direita .
- Siga os passos acima até que o tamanho correto seja menor que o tamanho da array.
O índice inicial e o comprimento fornecem a subarray resultante no final.
Implementação:
// C++ implementation of problem to find a sub-array with
// given sum.
#include <bits/stdc++.h>
using namespace std;
// Implementation function
void smallestSubArrayWithGivenSum(vector<int>& arr,
int reqSum)
{
// There would be no sub-array as an answer
// if the array in the question is empty.
if (arr.size() == 0) {
cout << "There exists no sub-array with sum="
<< reqSum << "\n";
return;
}
// Initializing variables.
int len = INT_MAX, left = 0, right = 0, startIndex = -1,
currSum = arr[0], n = arr.size();
// Traversing the array.
while (right < n) {
// When both the index-holders have
// the same value.
if (left == right) {
// Modifying length and startingIndex
// both both 'left' and 'right' are
// same and have the value of the
// required sum.
if (currSum == reqSum) {
len = min(1, len);
startIndex = left;
}
// Incrementing 'right; and adding the
// value at that index to the current
// sum.
right++;
currSum += arr[right];
continue;
}
// Dropping the element at index 'left'
// from the current sum if current sum
// becomes greater than the required value.
if (currSum > reqSum) {
currSum -= arr[left];
left++;
}
else {
// Modifying length and starting index
// if current sum is equal to the required
// sum.
if (reqSum == currSum
&& right - left + 1 < len) {
len = min(len, right - left + 1);
startIndex = left;
}
// Incrementing 'right; and adding the
// value at that index to the current
// sum.
right++;
currSum += arr[right];
}
}
// If the length of the answer sub-array results over
// the length of the initial array, it means that the
// answer does not exist.
if (len > n) {
cout << "There exists no sub-array with sum="
<< reqSum << "\n";
return;
}
// Printing the answer sub-array.
cout << "The smallest sub-array with sum = " << reqSum
<< " is: ";
for (int i = startIndex; i < startIndex + len; i++)
cout << arr[i] << " ";
}
// Driver code
int main()
{
vector<int> arr = { 2, 4, 6, 10, 2, 1 };
int K = 12;
smallestSubArrayWithGivenSum(arr, K);
return 0;
}Saída
A menor subarray com soma = 6 é: 2 4
Complexidade de tempo: O (N)
Espaço auxiliar: O (1)
As postagens do blog Acervo Lima te ajudaram? Nos ajude a manter o blog no ar!
Faça uma doação para manter o blog funcionando.
70% das doações são no valor de R$ 5,00...
Diógenes Lima da Silva
