El subarreglo más largo que tiene la suma K | conjunto 2

Posted on by Rudeus Greyrat

Dada una array arr[] de tamaño N que contiene números enteros. La tarea es encontrar la longitud del subarreglo más largo que tenga una suma igual al valor K dado .

Ejemplos: 

Entrada: arr[] = {2, 3, 4, 2, 1, 1}, K = 10 
Salida: 4 
Explicación: 
El subarreglo {3, 4, 2, 1} da una suma de 10.

Entrada: arr[] = {6, 8, 14, 9, 4, 11, 10}, K = 13 
Salida: 2 
Explicación: 
El subarreglo {9, 4} da la suma como 13. 
 

Enfoque ingenuo: consulte este artículo.
Complejidad de Tiempo: O(N 2 )  
Espacio Auxiliar: O(1)

Enfoque eficiente: la idea es utilizar la búsqueda binaria para encontrar el subarreglo de longitud máxima que tenga la suma K . A continuación se muestran los pasos:

  1. Cree una array de suma de prefijos (por ejemplo , pref[] ) a partir de la array dada arr[] .
  2. Para cada elemento en la array de prefijos pref[] realice una búsqueda binaria: 
    • Inicialice las variables ans , start y end como -1, 0 y N respectivamente.
    • Encuentre el índice medio (digamos mid ).
    • Si pref[mid] – val ≤ K entonces actualice la variable de inicio a mid + 1 y ans a mid .
    • De lo contrario, actualice la variable final a mid – 1 .
  3. Devuelve el valor de ans de la búsqueda binaria anterior.
  4. Si la longitud actual del subarreglo es menor que (ans – i) , entonces actualice la longitud máxima a (ans – i) .

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

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// To store the prefix sum array
vector<int> v;
 
// Function for searching the
// lower bound of the subarray
int bin(int val, int k, int n)
{
    int lo = 0;
    int hi = n;
    int mid;
    int ans = -1;
 
    // Iterate until low less
    // than equal to high
    while (lo <= hi) {
        mid = lo + (hi - lo) / 2;
 
        // For each mid finding sum
        // of sub array less than
        // or equal to k
        if (v[mid] - val <= k) {
            lo = mid + 1;
            ans = mid;
        }
        else
            hi = mid - 1;
    }
 
    // Return the final answer
    return ans;
}
 
// Function to find the length of
// subarray with sum K
void findSubarraySumK(int arr[], int N, int K)
{
 
    // Initialize sum to 0
    int sum = 0;
    v.push_back(0);
 
    // Push the prefix sum of the
    // array arr[] in prefix[]
    for (int i = 0; i < N; i++) {
 
        sum += arr[i];
        v.push_back(sum);
    }
 
    int l = 0, ans = 0, r;
 
    for (int i = 0; i < N; i++) {
 
        // Search r for each i
        r = bin(v[i], K, N);
 
        // Update ans
        ans = max(ans, r - i);
    }
 
    // Print the length of subarray
    // found in the array
    cout << ans;
}
 
// Driver Code
int main()
{
    // Given array arr[]
    int arr[] = { 6, 8, 14, 9, 4, 11, 10 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Given sum K
    int K = 13;
 
    // Function Call
    findSubarraySumK(arr, N, K);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG {
 
    // To store the prefix sum array
    static Vector<Integer> v = new Vector<Integer>();
 
    // Function for searching the
    // lower bound of the subarray
    static int bin(int val, int k, int n)
    {
        int lo = 0;
        int hi = n;
        int mid;
        int ans = -1;
 
        // Iterate until low less
        // than equal to high
        while (lo <= hi) {
            mid = lo + (hi - lo) / 2;
 
            // For each mid finding sum
            // of sub array less than
            // or equal to k
            if (v.get(mid) - val <= k) {
                lo = mid + 1;
                ans = mid;
            }
            else
                hi = mid - 1;
        }
 
        // Return the final answer
        return ans;
    }
 
    // Function to find the length of
    // subarray with sum K
    static void findSubarraySumK(int arr[], int N, int K)
    {
 
        // Initialize sum to 0
        int sum = 0;
        v.add(0);
 
        // Push the prefix sum of the
        // array arr[] in prefix[]
        for (int i = 0; i < N; i++) {
            sum += arr[i];
            v.add(sum);
        }
 
        int l = 0, ans = 0, r;
 
        for (int i = 0; i < v.size(); i++) {
 
            // Search r for each i
            r = bin(v.get(i), K, N);
 
            // Update ans
            ans = Math.max(ans, r - i);
        }
 
        // Print the length of subarray
        // found in the array
        System.out.print(ans);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        // Given array arr[]
        int arr[] = { 6, 8, 14, 9, 4, 11, 10 };
 
        int N = arr.length;
 
        // Given sum K
        int K = 13;
 
        // Function call
        findSubarraySumK(arr, N, K);
    }
}
 
// This code is contributed by gauravrajput1

Python3

# Python3 program for the above approach
 
# To store the prefix sum1 array
v = []
 
# Function for searching the
# lower bound of the subarray
 
 
def bin1(val, k, n):
 
    global v
    lo = 0
    hi = n
    mid = 0
    ans = -1
 
    # Iterate until low less
    # than equal to high
    while (lo <= hi):
        mid = lo + ((hi - lo) // 2)
 
        # For each mid finding sum1
        # of sub array less than
        # or equal to k
        if (v[mid] - val <= k):
            lo = mid + 1
            ans = mid
        else:
            hi = mid - 1
 
    # Return the final answer
    return ans
 
# Function to find the length of
# subarray with sum1 K
 
 
def findSubarraysum1K(arr, N, K):
 
    global v
 
    # Initialize sum1 to 0
    sum1 = 0
    v.append(0)
 
    # Push the prefix sum1 of the
    # array arr[] in prefix[]
    for i in range(N):
        sum1 += arr[i]
        v.append(sum1)
 
    l = 0
    ans = 0
    r = 0
 
    for i in range(len(v)):
 
        # Search r for each i
        r = bin1(v[i], K, N)
 
        # Update ans
        ans = max(ans, r - i)
 
    # Print the length of subarray
    # found in the array
    print(ans)
 
 
# Driver Code
if __name__ == '__main__':
 
    # Given array arr[]
    arr = [6, 8, 14, 9, 4, 11, 10]
 
    N = len(arr)
 
    # Given sum1 K
    K = 13
 
    # Function Call
    findSubarraysum1K(arr, N, K)
 
# This code is contributed by ipg2016107

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG {
 
    // To store the prefix sum array
    static List<int> v = new List<int>();
 
    // Function for searching the
    // lower bound of the subarray
    static int bin(int val, int k, int n)
    {
        int lo = 0;
        int hi = n;
        int mid;
        int ans = -1;
 
        // Iterate until low less
        // than equal to high
        while (lo <= hi) {
            mid = lo + (hi - lo) / 2;
 
            // For each mid finding sum
            // of sub array less than
            // or equal to k
            if (v[mid] - val <= k) {
                lo = mid + 1;
                ans = mid;
            }
            else
                hi = mid - 1;
        }
 
        // Return the final answer
        return ans;
    }
 
    // Function to find the length of
    // subarray with sum K
    static void findSubarraySumK(int[] arr, int N, int K)
    {
 
        // Initialize sum to 0
        int sum = 0;
        v.Add(0);
 
        // Push the prefix sum of the
        // array []arr in prefix[]
        for (int i = 0; i < N; i++) {
            sum += arr[i];
            v.Add(sum);
        }
 
        int ans = 0, r;
 
        for (int i = 0; i < v.Count; i++) {
 
            // Search r for each i
            r = bin(v[i], K, N);
 
            // Update ans
            ans = Math.Max(ans, r - i);
        }
 
        // Print the length of subarray
        // found in the array
        Console.Write(ans);
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
 
        // Given array []arr
        int[] arr = { 6, 8, 14, 9, 4, 11, 10 };
 
        int N = arr.Length;
 
        // Given sum K
        int K = 13;
 
        // Function call
        findSubarraySumK(arr, N, K);
    }
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
// Javascript program for the above approach
 
// To store the prefix sum array
let v = [];
 
// Function for searching the
// lower bound of the subarray
function bin(val, k, n)
{
    let lo = 0;
    let hi = n;
    let mid;
    let ans = -1;
 
    // Iterate until low less
    // than equal to high
    while (lo <= hi) {
        mid = lo + parseInt((hi - lo) / 2);
 
        // For each mid finding sum
        // of sub array less than
        // or equal to k
        if (v[mid] - val <= k) {
            lo = mid + 1;
            ans = mid;
        }
        else
            hi = mid - 1;
    }
 
    // Return the final answer
    return ans;
}
 
// Function to find the length of
// subarray with sum K
function findSubarraySumK(arr, N, K)
{
 
    // Initialize sum to 0
    let sum = 0;
    v.push(0);
 
    // Push the prefix sum of the
    // array arr[] in prefix[]
    for (let i = 0; i < N; i++) {
 
        sum += arr[i];
        v.push(sum);
    }
 
    let l = 0, ans = 0, r;
 
    for (let i = 0; i < N; i++) {
 
        // Search r for each i
        r = bin(v[i], K, N);
 
        // Update ans
        ans = Math.max(ans, r - i);
    }
 
    // Print the length of subarray
    // found in the array
    document.write(ans);
}
 
// Driver Code
    // Given array arr[]
    let arr = [ 6, 8, 14, 9, 4, 11, 10 ];
 
    let N = arr.length;
 
    // Given sum K
    let K = 13;
 
    // Function Call
    findSubarraySumK(arr, N, K);
     
</script>
Producción

2

Complejidad de tiempo: O(N*log 2 N)  
Espacio auxiliar: O(N)

Enfoque eficiente: para un enfoque O(N) , consulte el enfoque eficiente de este artículo.
 

Publicación traducida automáticamente

Artículo escrito por asknishant y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *