Dada una array arr[] de tamaño n que contiene números enteros. El problema es encontrar la longitud del subarreglo más largo que tenga una suma igual al valor k dado .
Ejemplos:
Input : arr[] = { 10, 5, 2, 7, 1, 9 },
k = 15
Output : 4
The sub-array is {5, 2, 7, 1}.
Input : arr[] = {-5, 8, -14, 2, 4, 12},
k = -5
Output : 5
Enfoque ingenuo: Considere la suma de todos los subconjuntos y devuelva la longitud del subarreglo más largo que tenga la suma ‘k’. La complejidad del tiempo es de O (n ^ 2).
Enfoque eficiente:
Los siguientes son los pasos:
- Inicialice sum = 0 y maxLen = 0.
- Cree una tabla hash que tenga tuplas (suma, índice) .
- Para i = 0 a n-1, realice los siguientes pasos:
- Acumule arr[i] a sum .
- Si sum == k, actualice maxLen = i+1.
- Compruebe si la suma está presente en la tabla hash o no. Si no está presente, agréguelo a la tabla hash como (suma, i) par.
- Compruebe si (sum-k) está presente en la tabla hash o no. Si está presente, obtenga el índice de (sum-k) de la tabla hash como índice . Ahora verifique si maxLen < (i-index), luego actualice maxLen = (i-index).
- Devuelve maxLen .
Implementación:
C++
// C++ implementation to find the length
// of longest subarray having sum k
#include <bits/stdc++.h>
using namespace std;
// function to find the length of longest
// subarray having sum k
int lenOfLongSubarr(int arr[],
int n,
int k)
{
// unordered_map 'um' implemented
// as hash table
unordered_map<int, int> um;
int sum = 0, maxLen = 0;
// traverse the given array
for (int i = 0; i < n; i++) {
// accumulate sum
sum += arr[i];
// when subarray starts from index '0'
if (sum == k)
maxLen = i + 1;
// make an entry for 'sum' if it is
// not present in 'um'
if (um.find(sum) == um.end())
um[sum] = i;
// check if 'sum-k' is present in 'um'
// or not
if (um.find(sum - k) != um.end()) {
// update maxLength
if (maxLen < (i - um[sum - k]))
maxLen = i - um[sum - k];
}
}
// required maximum length
return maxLen;
}
// Driver Code
int main()
{
int arr[] = {10, 5, 2, 7, 1, 9};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 15;
cout << "Length = "
<< lenOfLongSubarr(arr, n, k);
return 0;
}
Java
// Java implementation to find the length
// of longest subarray having sum k
import java.io.*;
import java.util.*;
class GFG {
// function to find the length of longest
// subarray having sum k
static int lenOfLongSubarr(int[] arr, int n, int k)
{
// HashMap to store (sum, index) tuples
HashMap<Integer, Integer> map = new HashMap<>();
int sum = 0, maxLen = 0;
// traverse the given array
for (int i = 0; i < n; i++) {
// accumulate sum
sum += arr[i];
// when subarray starts from index '0'
if (sum == k)
maxLen = i + 1;
// make an entry for 'sum' if it is
// not present in 'map'
if (!map.containsKey(sum)) {
map.put(sum, i);
}
// check if 'sum-k' is present in 'map'
// or not
if (map.containsKey(sum - k)) {
// update maxLength
if (maxLen < (i - map.get(sum - k)))
maxLen = i - map.get(sum - k);
}
}
return maxLen;
}
// Driver code
public static void main(String args[])
{
int[] arr = {10, 5, 2, 7, 1, 9};
int n = arr.length;
int k = 15;
System.out.println("Length = " +
lenOfLongSubarr(arr, n, k));
}
}
// This code is contributed by rachana soma
Python3
# Python3 implementation to find the length
# of longest subArray having sum k
# function to find the longest
# subarray having sum k
def lenOfLongSubarr(arr, n, k):
# dictionary mydict implemented
# as hash map
mydict = dict()
# Initialize sum and maxLen with 0
sum = 0
maxLen = 0
# traverse the given array
for i in range(n):
# accumulate the sum
sum += arr[i]
# when subArray starts from index '0'
if (sum == k):
maxLen = i + 1
# check if 'sum-k' is present in
# mydict or not
elif (sum - k) in mydict:
maxLen = max(maxLen, i - mydict[sum - k])
# if sum is not present in dictionary
# push it in the dictionary with its index
if sum not in mydict:
mydict[sum] = i
return maxLen
# Driver Code
if __name__ == '__main__':
arr = [10, 5, 2, 7, 1, 9]
n = len(arr)
k = 15
print("Length =", lenOfLongSubarr(arr, n, k))
# This code is contributed by
# chaudhary_19 (Mayank Chaudhary)
C#
// C# implementation to find the length
// of longest subarray having sum k
using System;
using System.Collections.Generic;
class GFG
{
// function to find the length of longest
// subarray having sum k
static int lenOfLongSubarr(int[] arr,
int n, int k)
{
// HashMap to store (sum, index) tuples
Dictionary<int,
int> map = new Dictionary<int,
int>();
int sum = 0, maxLen = 0;
// traverse the given array
for (int i = 0; i < n; i++)
{
// accumulate sum
sum += arr[i];
// when subarray starts from index '0'
if (sum == k)
maxLen = i + 1;
// make an entry for 'sum' if it is
// not present in 'map'
if (!map.ContainsKey(sum))
{
map.Add(sum, i);
}
// check if 'sum-k' is present in 'map'
// or not
if (map.ContainsKey(sum - k))
{
// update maxLength
if (maxLen < (i - map[sum - k]))
maxLen = i - map[sum - k];
}
}
return maxLen;
}
// Driver code
public static void Main()
{
int[] arr = {10, 5, 2, 7, 1, 9};
int n = arr.Length;
int k = 15;
Console.WriteLine("Length = " +
lenOfLongSubarr(arr, n, k));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript implementation to find the length
// of longest subarray having sum k
// function to find the length of longest
// subarray having sum k
function lenOfLongSubarr(arr, n, k)
{
// unordered_map 'um' implemented
// as hash table
var um = new Map();
var sum = 0, maxLen = 0;
// traverse the given array
for (var i = 0; i < n; i++) {
// accumulate sum
sum += arr[i];
// when subarray starts from index '0'
if (sum == k)
maxLen = i + 1;
// make an entry for 'sum' if it is
// not present in 'um'
if (!um.has(sum))
um.set(sum, i);
// check if 'sum-k' is present in 'um'
// or not
if (um.has(sum - k)) {
// update maxLength
if (maxLen < (i - um.get(sum - k)))
maxLen = i - um.get(sum - k);
}
}
// required maximum length
return maxLen;
}
// Driver Code
var arr = [10, 5, 2, 7, 1, 9];
var n = arr.length;
var k = 15;
document.write( "Length = "
+ lenOfLongSubarr(arr, n, k));
</script>
Producción
Length = 4
Complejidad temporal: O(n).
Espacio Auxiliar: O(n).
Otro enfoque
Este enfoque no funcionará para números negativos.
El enfoque es usar el concepto de la ventana deslizante de tamaño variable usando 2 punteros
Inicialice i, j y suma = k. Si la suma es menor que k, simplemente incremente j, si la suma es igual a k, calcule el máximo
y si la suma es mayor que k se resta el i-ésimo elemento mientras la suma es menor que k.
Implementación:
C++
// C++ implementation to find the length
// of longest subarray having sum k
#include <bits/stdc++.h>
using namespace std;
// function to find the length of longest
// subarray having sum k
int lenOfLongSubarr(int A[], int N, int K)
{
int i = 0, j = 0, sum = 0;
int maxLen = INT_MIN;
while (j < N) {
sum += A[j];
if (sum < K) {
j++;
}
else if (sum == K) {
maxLen = max(maxLen, j-i+1);
j++;
}
else if (sum > K) {
while (sum > K) {
sum -= A[i];
i++;
}
if(sum == K){
maxLen = max(maxLen, j-i+1);
}
j++;
}
}
return maxLen;
}
// Driver Code
int main()
{
int arr[] = { 10, 5, 2, 7, 1, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 15;
cout << "Length = " << lenOfLongSubarr(arr, n, k);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
// Java implementation to find the length
// of longest subarray having sum k
// function to find the length of longest
// subarray having sum k
static int lenOfLongSubarr(int A[], int N, int K)
{
int i = 0, j = 0, sum = 0;
int maxLen = Integer.MIN_VALUE;
while (j < N) {
sum += A[j];
if (sum < K) {
j++;
}
else if (sum == K) {
maxLen = Math.max(maxLen, j-i+1);
j++;
}
else if (sum > K) {
while (sum > K) {
sum -= A[i];
i++;
}
if(sum == K){
maxLen = Math.max(maxLen, j-i+1);
}
j++;
}
}
return maxLen;
}
// Driver code
public static void main(String args[])
{
int arr[] = { 10, 5, 2, 7, 1, 9 };
int n = arr.length;
int k = 15;
System.out.printf("Length = %d",lenOfLongSubarr(arr, n, k));
}
}
// This code is contributed by shinjanpatra.
Python3
# Python implementation to find the length
# of longest subarray having sum k
# function to find the length of longest
# subarray having sum k
import sys
def lenOfLongSubarr(A, N, K):
i, j, sum = 0, 0, 0
maxLen = -sys.maxsize -1
while (j < N):
sum += A[j]
if (sum < K):
j += 1
elif (sum == K):
maxLen = max(maxLen, j - i + 1)
j += 1
elif (sum > K):
while (sum > K):
sum -= A[i]
i += 1
if (sum == K):
maxLen = max(maxLen, j - i + 1)
j += 1
return maxLen
# Driver Code
arr = [ 10, 5, 2, 7, 1, 9 ]
n = len(arr)
k = 15
print("Length = "+ str(lenOfLongSubarr(arr, n, k)))
# This code is contributed by shinjanpatra
C#
// C# code for the above approach
using System;
public class GFG {
// function to find the length of longest subarray
// having sum k
static int lenOfLongSubarr(int[] A, int N, int K)
{
int i = 0, j = 0, sum = 0;
int maxLen = Int32.MinValue;
while (j < N) {
sum += A[j];
if (sum < K) {
j++;
}
else if (sum == K) {
maxLen = Math.Max(maxLen, j - i + 1);
j++;
}
else if (sum > K) {
while (sum > K) {
sum -= A[i];
i++;
}
if (sum == K) {
maxLen = Math.Max(maxLen, j - i + 1);
}
j++;
}
}
return maxLen;
}
static public void Main()
{
// Code
int[] arr = { 10, 5, 2, 7, 1, 9 };
int n = arr.Length;
int k = 15;
Console.Write("Length = "
+ lenOfLongSubarr(arr, n, k));
}
}
// This code is contributed by lokesh (lokeshmvs21).
Javascript
<script>
// JavaScript implementation to find the length
// of longest subarray having sum k
// function to find the length of longest
// subarray having sum k
function lenOfLongSubarr(A, N, K)
{
let i = 0, j = 0, sum = 0;
let maxLen = Number.MIN_VALUE;
while (j < N) {
sum += A[j];
if (sum < K) {
j++;
}
else if (sum == K) {
maxLen = Math.max(maxLen, j-i+1);
j++;
}
else if (sum > K) {
while (sum > K) {
sum -= A[i];
i++;
}
if(sum == K){
maxLen = Math.max(maxLen, j-i+1);
}
j++;
}
}
return maxLen;
}
// Driver Code
let arr = [ 10, 5, 2, 7, 1, 9 ]
let n = arr.length
let k = 15
document.write("Length = ",lenOfLongSubarr(arr, n, k))
// This code is contributed by shinjanpatra
</script>
Producción
Length = 4
Complejidad temporal: O(n).
Espacio Auxiliar: O(1).
Publicación traducida automáticamente
Artículo escrito por ayushjauhari14 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA