Рубрики

Наименьший подмассив с суммой, превышающей заданное значение

Учитывая массив целых чисел и число x, найдите наименьший подмассив с суммой, большей чем данное значение.

Examples:
arr[] = {1, 4, 45, 6, 0, 19}
   x  =  51
Output: 3
Minimum length subarray is {4, 45, 6}

arr[] = {1, 10, 5, 2, 7}
   x  = 9
Output: 1
Minimum length subarray is {10}

arr[] = {1, 11, 100, 1, 0, 200, 3, 2, 1, 250}
    x = 280
Output: 4
Minimum length subarray is {100, 1, 0, 200}

arr[] = {1, 2, 4}
    x = 8
Output : Not Possible
Whole array sum is smaller than 8.

Простым решением является использование двух вложенных циклов. Внешний цикл выбирает начальный элемент, внутренний цикл рассматривает все элементы (справа от текущего начала) как конечный элемент. Всякий раз, когда сумма элементов между текущим началом и концом становится больше заданного числа, обновите результат, если текущая длина меньше самой маленькой длины на данный момент.
Ниже приводится реализация простого подхода.

С

# include <iostream>

using namespace std;

  
// Возвращает длину наименьшего подмассива с суммой, превышающей x.
// Если нет подмассива с заданной суммой, то возвращает n + 1

int smallestSubWithSum(int arr[], int n, int x)

{

    // Инициализируем длину наименьшего подмассива как n + 1

     int min_len = n + 1;

  

     // Выбрать каждый элемент в качестве отправной точки

     for (int start=0; start<n; start++)

     {

          // Инициализировать сумму, начиная с текущего старта

          int curr_sum = arr[start];

  

          // Если первый элемент больше

          if (curr_sum > x) return 1;

  

          // Попробуем разные конечные точки для начала curremt

          for (int end=start+1; end<n; end++)

          {

              // добавляем последний элемент к текущей сумме

              curr_sum += arr[end];

  

              // Если сумма становится больше чем x и длина

              // этот подмассив меньше текущего наименьшего

              // длина, обновить наименьшую длину (или результат)

              if (curr_sum > x && (end - start + 1) < min_len)

                 min_len = (end - start + 1);

          }

     }

     return min_len;

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

    int arr1[] = {1, 4, 45, 6, 10, 19};

    int x = 51;

    int n1 = sizeof(arr1)/sizeof(arr1[0]);

    int res1 = smallestSubWithSum(arr1, n1, x);

    (res1 == n1+1)? cout << "Not possible\n" :

                    cout << res1 << endl;

  

    int arr2[] = {1, 10, 5, 2, 7};

    int n2 = sizeof(arr2)/sizeof(arr2[0]);

    x  = 9;

    int res2 = smallestSubWithSum(arr2, n2, x);

    (res2 == n2+1)? cout << "Not possible\n" :

                    cout << res2 << endl;

  

    int arr3[] = {1, 11, 100, 1, 0, 200, 3, 2, 1, 250};

    int n3 = sizeof(arr3)/sizeof(arr3[0]);

    x  = 280;

    int res3 = smallestSubWithSum(arr3, n3, x);

    (res3 == n3+1)? cout << "Not possible\n" :

                    cout << res3 << endl;

  

    return 0;

}

Джава

class SmallestSubArraySum

{

    // Возвращает длину наименьшего подмассива с суммой, превышающей x.

    // Если нет подмассива с заданной суммой, то возвращает n + 1

    static int smallestSubWithSum(int arr[], int n, int x)

    {

        // Инициализируем длину наименьшего подмассива как n + 1

        int min_len = n + 1;

  

        // Выбрать каждый элемент в качестве отправной точки

        for (int start = 0; start < n; start++)

        {

            // Инициализировать сумму, начиная с текущего старта

            int curr_sum = arr[start];

  

            // Если первый элемент больше

            if (curr_sum > x)

                return 1;

  

            // Попробуем разные конечные точки для начала curremt

            for (int end = start + 1; end < n; end++)

            {

                // добавляем последний элемент к текущей сумме

                curr_sum += arr[end];

  

                // Если сумма становится больше чем x и длина

                // этот подмассив меньше текущего наименьшего

                // длина, обновить наименьшую длину (или результат)

                if (curr_sum > x && (end - start + 1) < min_len)

                    min_len = (end - start + 1);

            }

        }

        return min_len;

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String[] args)

    {

        int arr1[] = {1, 4, 45, 6, 10, 19};

        int x = 51;

        int n1 = arr1.length;

        int res1 = smallestSubWithSum(arr1, n1, x);

        if (res1 == n1+1)

           System.out.println("Not Possible");

        else

           System.out.println(res1);

  

  

        int arr2[] = {1, 10, 5, 2, 7};

        int n2 = arr2.length;

        x = 9;

        int res2 = smallestSubWithSum(arr2, n2, x);

        if (res2 == n2+1)

           System.out.println("Not Possible");

        else

           System.out.println(res2);

  

        int arr3[] = {1, 11, 100, 1, 0, 200, 3, 2, 1, 250};

        int n3 = arr3.length;

        x = 280;

        int res3 = smallestSubWithSum(arr3, n3, x);

        if (res3 == n3+1)

           System.out.println("Not Possible");

        else

           System.out.println(res3);

    }

}

  
// Этот код предоставлен Mayank Jaiswal

python3

# Python3 программа для поиска самых маленьких
# подмассив с суммой большей
# чем заданное значение

  
# Возвращает длину наименьшего подмассива
# с суммой больше х. Если здесь
# не является подмассивом с заданной суммой,
# затем возвращает n + 1

def smallestSubWithSum(arr, n, x):

  

    # Инициализировать длину наименьшего

    # подрешетка при n + 1

    min_len = n + 1

  

    # Выберите каждый элемент в качестве отправной точки

    for start in range(0,n):

      

        # Инициализировать начальную сумму

        # с текущим началом

        curr_sum = arr[start]

  

        # Если первый элемент больше

        if (curr_sum > x):

            return 1

  

        # Попробуйте разные конечные точки

        # для старта

        for end in range(start+1,n):

          

            # добавить последний элемент к текущей сумме

            curr_sum += arr[end]

  

            # Если сумма становится больше, чем х

            # и длина этого подмассива

            # меньше текущего наименьшего

            # длина, обновить наименьшее

            # длина (или результат)

            if curr_sum > x and (end - start + 1) < min_len:

                min_len = (end - start + 1)

          

    return min_len;

  

  
# Программа драйвера для проверки вышеуказанной функции * /

arr1 = [1, 4, 45, 6, 10, 19]

x = 51

n1 = len(arr1)

res1 = smallestSubWithSum(arr1, n1, x);

if res1 == n1+1:

    print("Not possible")

else:

    print(res1)

  

arr2 = [1, 10, 5, 2, 7]

n2 = len(arr2)

x = 9

res2 = smallestSubWithSum(arr2, n2, x);

if res2 == n2+1:

    print("Not possible")

else:

    print(res2)

  

arr3 = [1, 11, 100, 1, 0, 200, 3, 2, 1, 250]

n3 = len(arr3)

x = 280

res3 = smallestSubWithSum(arr3, n3, x)

if res3 == n3+1:

    print("Not possible"

else:

    print(res3)

      
# Этот код предоставлен Смитой Динеш Семвал

C #

// C # программа для поиска наименьшего
// подрешетка с большей суммой
// чем заданное значение

using System;

  

class GFG

{

      

    // Возвращает длину наименьшего

    // подрешетка с большей суммой

    // чем х. Если нет

    // подрешетка с заданной суммой,

    // затем возвращает n + 1

    static int smallestSubWithSum(int []arr, 

                                  int n, int x)

    {

        // Инициализировать длину

        // наименьший подмассив при n + 1

        int min_len = n + 1;

  

        // Выбрать каждый элемент

        // в качестве отправной точки

        for (int start = 0; start < n; start++)

        {

            // Инициализируем начальную сумму

            // с текущим началом

            int curr_sum = arr[start];

  

            // Если первый элемент

            // сам по себе больше

            if (curr_sum > x)

                return 1;

  

            // Попробуйте другое окончание

            // очки для старта

            for (int end = start + 1; 

                     end < n; end++)

            {

                // добавить последний элемент

                // к текущей сумме

                curr_sum += arr[end];

  

                // Если сумма становится больше чем

                // х и длина этого

                // подрешетка меньше чем

                // текущая наименьшая длина,

                // обновить наименьшее

                // длина (или результат)

                if (curr_sum > x && 

                        (end - start + 1) < min_len)

                    min_len = (end - start + 1);

            }

        }

        return min_len;

    }

  

    // Код драйвера

    static public void Main ()

    {

        int []arr1 = {1, 4, 45, 

                      6, 10, 19};

        int x = 51;

        int n1 = arr1.Length;

        int res1 = smallestSubWithSum(arr1, 

                                      n1, x);

        if (res1 == n1 + 1)

        Console.WriteLine("Not Possible");

        else

        Console.WriteLine(res1);

  

  

        int []arr2 = {1, 10, 5, 2, 7};

        int n2 = arr2.Length;

        x = 9;

        int res2 = smallestSubWithSum(arr2, 

                                      n2, x);

        if (res2 == n2 + 1)

        Console.WriteLine("Not Possible");

        else

        Console.WriteLine(res2);

  

        int []arr3 = {1, 11, 100, 1, 0, 

                      200, 3, 2, 1, 250};

        int n3 = arr3.Length;

        x = 280;

        int res3 = smallestSubWithSum(arr3, 

                                      n3, x);

        if (res3 == n3 + 1)

        Console.WriteLine("Not Possible");

        else

        Console.WriteLine(res3);

    }

}

  
// Этот код предоставлен ajit

PHP

<?php
// Возвращает длину наименьшего
// подрешетка с большей суммой
// чем х. Если нет
// подрешетка с заданной суммой,
// затем возвращает n + 1

function smallestSubWithSum($arr, $n, $x)

{

    // Инициализировать длину

    // наименьший подмассив при n + 1

    $min_len = $n + 1;

  

    // Выбрать каждый элемент

    // в качестве отправной точки

    for ($start = 0; $start < $n; $start++)

    {

        // Инициализируем начальную сумму

        // с текущим началом

        $curr_sum = $arr[$start];

  

        // Если первый элемент

        // сам по себе больше

        if ($curr_sum > $x) return 1;

  

        // Попробуйте другое окончание

        // очки для старта

        for ($end= $start + 1; $end < $n; $end++)

        {

            // добавить последний элемент

            // к текущей сумме

            $curr_sum += $arr[$end];

  

            // Если сумма становится больше чем

            // x и длина этого подмассива

            // меньше текущего

            // наименьшая длина, обновите

            // наименьшая длина (или результат)

            if ($curr_sum > $x && 

                   ($end - $start + 1) < $min_len)

                $min_len = ($end - $start + 1);

        }

    }

    return $min_len;

}

  
// Код драйвера

$arr1 = array (1, 4, 45, 

               6, 10, 19);

$x = 51;

$n1 = sizeof($arr1);

$res1 = smallestSubWithSum($arr1, $n1, $x);

  

if (($res1 == $n1 + 1) == true)

    echo "Not possible\n" ;

else

    echo $res1 , "\n";

  

$arr2 = array(1, 10, 5, 2, 7);

$n2 = sizeof($arr2);

$x = 9;

$res2 = smallestSubWithSum($arr2, $n2, $x);

  

if (($res2 == $n2 + 1) == true) 

    echo "Not possible\n" ;

else

    echo $res2 , "\n";

  

$arr3 = array (1, 11, 100, 1, 0,

               200, 3, 2, 1, 250);

$n3 = sizeof($arr3);

$x = 280;

$res3 = smallestSubWithSum($arr3, $n3, $x);

if (($res3 == $n3 + 1) == true)

    echo "Not possible\n" ;

else

    echo $res3 , "\n";

  
// Этот код предоставлен ajit
?>


Выход:

3
1
4 

Сложность времени: временная сложность вышеописанного подхода явно O (n 2 ).

Эффективное решение: эта проблема может быть решена за O (n) раз, используя идею, использованную в этом посте. Спасибо Ankit и Nitin за предложение этого оптимизированного решения.

C ++

// O (n) решение для поиска наименьшего подмассива с суммой
// больше чем х
#include <iostream>

using namespace std;

  
// Возвращает длину наименьшего подмассива с суммой, превышающей x.
// Если нет подмассива с заданной суммой, то возвращает n + 1

int smallestSubWithSum(int arr[], int n, int x)

{

    // Инициализируем текущую сумму и минимальную длину

    int curr_sum = 0, min_len = n+1;

  

    // Инициализировать начальный и конечный индексы

    int start = 0, end = 0;

    while (end < n)

    {

        // Продолжаем добавлять элементы массива при текущей сумме

        // меньше чем х

        while (curr_sum <= x && end < n)

            curr_sum += arr[end++];

  

        // Если текущая сумма становится больше, чем х.

        while (curr_sum > x && start < n)

        {

            // Обновление минимальной длины, если необходимо

            if (end - start < min_len)

                min_len = end - start;

  

            // удаляем стартовые элементы

            curr_sum -= arr[start++];

        }

    }

    return min_len;

}

  

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

    int arr1[] = {1, 4, 45, 6, 10, 19};

    int x = 51;

    int n1 = sizeof(arr1)/sizeof(arr1[0]);

    int res1 = smallestSubWithSum(arr1, n1, x);

    (res1 == n1+1)? cout << "Not possible\n" :

                    cout << res1 << endl;

  

    int arr2[] = {1, 10, 5, 2, 7};

    int n2 = sizeof(arr2)/sizeof(arr2[0]);

    x  = 9;

    int res2 = smallestSubWithSum(arr2, n2, x);

    (res2 == n2+1)? cout << "Not possible\n" :

                    cout << res2 << endl;

  

    int arr3[] = {1, 11, 100, 1, 0, 200, 3, 2, 1, 250};

    int n3 = sizeof(arr3)/sizeof(arr3[0]);

    x  = 280;

    int res3 = smallestSubWithSum(arr3, n3, x);

    (res3 == n3+1)? cout << "Not possible\n" :

                    cout << res3 << endl;

  

    return 0;

}

Джава

// O (n) решение для поиска наименьшего подмассива с суммой
// больше чем х

  

class SmallestSubArraySum

{

    // Возвращает длину наименьшего подмассива с суммой, превышающей x.

    // Если нет подмассива с заданной суммой, то возвращает n + 1

    static int smallestSubWithSum(int arr[], int n, int x) 

    {

        // Инициализируем текущую сумму и минимальную длину

        int curr_sum = 0, min_len = n + 1;

  

        // Инициализировать начальный и конечный индексы

        int start = 0, end = 0;

        while (end < n) 

        {

            // Продолжаем добавлять элементы массива при текущей сумме

            // меньше чем х

            while (curr_sum <= x && end < n)

                curr_sum += arr[end++];

  

            // Если текущая сумма становится больше, чем х.

            while (curr_sum > x && start < n) 

            {

                // Обновление минимальной длины, если необходимо

                if (end - start < min_len)

                    min_len = end - start;

  

                // удаляем стартовые элементы

                curr_sum -= arr[start++];

            }

        }

        return min_len;

    }

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String[] args)

    {

        int arr1[] = {1, 4, 45, 6, 10, 19};

        int x = 51;

        int n1 = arr1.length;

        int res1 = smallestSubWithSum(arr1, n1, x);

        if (res1 == n1+1)

           System.out.println("Not Possible");

        else

           System.out.println(res1);

  

        int arr2[] = {1, 10, 5, 2, 7};

        int n2 = arr2.length;

        x = 9;

        int res2 = smallestSubWithSum(arr2, n2, x);

        if (res2 == n2+1)

           System.out.println("Not Possible");

        else

           System.out.println(res2);

  

        int arr3[] = {1, 11, 100, 1, 0, 200, 3, 2, 1, 250};

        int n3 = arr3.length;

        x = 280;

        int res3 = smallestSubWithSum(arr3, n3, x);

        if (res3 == n3+1)

           System.out.println("Not Possible");

        else

           System.out.println(res3);

    }

}

  
// Этот код предоставлен Mayank Jaiswal

python3

# O (n) решение для поиска наименьшего
# подрешетка с суммой больше чем x

  
# Возвращает длину наименьшего подмассива
# с суммой больше х. Если здесь
# не является подмассивом с заданной суммой, тогда
# возвращает n + 1

def smallestSubWithSum(arr, n, x):

  

    # Инициализировать текущую сумму и минимальную длину

    curr_sum = 0

    min_len = n + 1

  

    # Инициализировать начальный и конечный индексы

    start = 0

    end = 0

    while (end < n):

      

        # Продолжайте добавлять элементы массива в то время как текущий

        # сумма меньше чем х

        while (curr_sum <= x and end < n):

            curr_sum += arr[end]

            end+= 1

  

        # Если текущая сумма становится больше, чем х.

        while (curr_sum > x and start < n):

          

            # Обновите минимальную длину при необходимости

            if (end - start < min_len):

                min_len = end - start 

  

            # удалить стартовые элементы

            curr_sum -= arr[start]

            start+= 1

      

    return min_len 

  
# Драйверная программа

arr1 = [1, 4, 45, 6, 10, 19

x = 51

n1 = len(arr1) 

res1 = smallestSubWithSum(arr1, n1, x) 

print("Not possible") if (res1 == n1 + 1) else print(res1) 

  

arr2 = [1, 10, 5, 2, 7

n2 = len(arr2) 

x = 9

res2 = smallestSubWithSum(arr2, n2, x)

print("Not possible") if (res2 == n2 + 1) else print(res2) 

  

arr3 = [1, 11, 100, 1, 0, 200, 3, 2, 1, 250

n3 = len(arr3) 

x = 280

res3 = smallestSubWithSum(arr3, n3, x) 

print("Not possible") if (res3 == n3 + 1) else print(res3) 

  
# Этот код предоставлен
# Смита Динеш Семвал

C #

// O (n) решение для поиска
// наименьший подмассив с суммой
// больше чем х

using System;

  

class GFG

{

      

    // Возвращает длину наименьшего

    // подрешетка с большей суммой

    // чем х. Если нет

    // подрешетка с заданной суммой,

    // затем возвращает n + 1

    static int smallestSubWithSum(int []arr, 

                                  int n, int x) 

    {

        // Инициализируем текущий

        // сумма и минимальная длина

        int curr_sum = 0,

            min_len = n + 1;

  

        // Инициализация запуска

        // и конечные индексы

        int start = 0, end = 0;

        while (end < n) 

        {

            // Продолжаем добавлять элементы массива

            // пока текущая сумма меньше

            // чем х

            while (curr_sum <= x && end < n)

                curr_sum += arr[end++];

  

            // Если текущая сумма становится

            // больше чем х.

            while (curr_sum > x && start < n) 

            {

                // Обновление минимума

                // длина при необходимости

                if (end - start < min_len)

                    min_len = end - start;

  

                // удаляем стартовые элементы

                curr_sum -= arr[start++];

            }

        }

        return min_len;

    }

      

    // Код драйвера

    static public void Main ()

    {

        int []arr1 = {1, 4, 45, 

                      6, 10, 19};

        int x = 51;

        int n1 = arr1.Length;

        int res1 = smallestSubWithSum(arr1, 

                                      n1, x);

        if (res1 == n1 + 1)

        Console.WriteLine("Not Possible");

        else

        Console.WriteLine(res1);

  

        int []arr2 = {1, 10, 5, 2, 7};

        int n2 = arr2.Length;

        x = 9;

        int res2 = smallestSubWithSum(arr2,

                                      n2, x);

        if (res2 == n2 + 1)

        Console.WriteLine("Not Possible");

        else

        Console.WriteLine(res2);

  

        int []arr3 = {1, 11, 100, 1, 0,

                      200, 3, 2, 1, 250};

        int n3 = arr3.Length;

        x = 280;

        int res3 = smallestSubWithSum(arr3,

                                      n3, x);

        if (res3 == n3 + 1)

        Console.WriteLine("Not Possible");

        else

        Console.WriteLine(res3);

    }

}

  
// Этот код предоставлен akt_mit

PHP

<?php
// O (n) решение для поиска
// наименьший подмассив с суммой
// больше чем х

  
// Возвращает длину наименьшего
// подрешетка с большей суммой
// чем х. Если нет
// подрешетка с заданной суммой,
// затем возвращает n + 1

function smallestSubWithSum($arr

                            $n, $x)

{

    // Инициализируем текущий

    // сумма и минимальная длина

    $curr_sum = 0; 

    $min_len = $n + 1;

  

    // Инициализация запуска

    // и конечные индексы

    $start = 0;

    $end = 0;

    while ($end < $n)

    {

        // Продолжаем добавлять элементы массива

        // пока текущая сумма меньше

        // чем х

        while ($curr_sum <= $x && 

               $end < $n)

            $curr_sum += $arr[$end++];

  

        // Если текущая сумма становится

        // больше чем х.

        while ($curr_sum > $x &&

               $start < $n)

        {

            // Обновление минимума

            // длина при необходимости

            if ($end - $start < $min_len)

                $min_len = $end - $start;

  

            // удаляем стартовые элементы

            $curr_sum -= $arr[$start++];

        }

    }

    return $min_len;

}

  
// Код драйвера

$arr1 = array(1, 4, 45, 

              6, 10, 19);

$x = 51;

$n1 = sizeof($arr1);

$res1 = smallestSubWithSum($arr1

   

                           $n1, $x);

if($res1 == $n1 + 1) 

echo "Not possible\n" ;

else

echo $res1 ,"\n";

  

$arr2 = array(1, 10, 5, 2, 7);

$n2 = sizeof($arr2);

$x = 9;

$res2 = smallestSubWithSum($arr2

                           $n2, $x);

if($res2 == $n2 + 1) 

echo "Not possible\n" ;

else

echo $res2,"\n";

  

$arr3 = array(1, 11, 100, 1, 0, 

              200, 3, 2, 1, 250);

$n3 = sizeof($arr3);

$x = 280;

$res3 = smallestSubWithSum($arr3

                           $n3, $x);

                             

if($res3 == $n3 + 1)

echo "Not possible\n" ;

else

echo $res3, "\n";

  
// Этот код предоставлен ajit
?>


Выход:

3
1
4 

Как обрабатывать отрицательные числа?
Приведенное выше решение может не работать, если входной массив содержит отрицательные числа. Например, arr [] = {- 8, 1, 4, 2, -6}. Для обработки отрицательных чисел добавьте условие, чтобы игнорировать подмассивы с отрицательными суммами.

C ++

// O (n) решение для поиска наименьшего подмассива с суммой
// больше чем х
#include <iostream>

using namespace std;

  
// Возвращает длину наименьшего подмассива с суммой, превышающей x.
// Если нет подмассива с заданной суммой, то возвращает n + 1

int smallestSubWithSum(int arr[], int n, int x)

{

    // Инициализируем текущую сумму и минимальную длину

    int curr_sum = 0, min_len = n+1;

  

    // Инициализировать начальный и конечный индексы

    int start = 0, end = 0;

    while (end < n)

    {

        // Продолжаем добавлять элементы массива при текущей сумме

        // меньше чем х

        while (curr_sum <= x && end < n)

        {

            // Игнорируем подмассивы с отрицательной суммой, если

            // х положительный.

            if (curr_sum <= 0 && x > 0)

            {

                start = end;

                curr_sum = 0;

            }

  

            curr_sum += arr[end++];

        }

  

        // Если текущая сумма становится больше, чем х.

        while (curr_sum > x && start < n)

        {

            // Обновление минимальной длины, если необходимо

            if (end - start < min_len)

                min_len = end - start;

  

            // удаляем стартовые элементы

            curr_sum -= arr[start++];

        }

    }

    return min_len;

}

  

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

    int arr1[] = {- 8, 1, 4, 2, -6};

    int x = 6;

    int n1 = sizeof(arr1)/sizeof(arr1[0]);

    int res1 = smallestSubWithSum(arr1, n1, x);

    (res1 == n1+1)? cout << "Not possible\n" :

                    cout << res1 << endl;

  

    return 0;

}

Джава

// Java O (n) решение для
// найти наименьший подмассив
// с суммой больше чем x

import java.io.*;

  

class GFG 

{

      
// Возвращает длину наименьшего
// подрешетка с большей суммой
// чем х. Если нет
// подрешетка с заданной суммой,
// затем возвращает n + 1

static int smallestSubWithSum(int arr[], 

                              int n, int x)

{

    // Инициализируем текущий

    // сумма и минимальная длина

    int curr_sum = 0, min_len = n + 1;

  

    // Инициализация запуска

    // и конечные индексы

    int start = 0, end = 0;

    while (end < n)

    {

        // Продолжаем добавлять массив

        // элементы при текущем

        // сумма меньше чем х

        while (curr_sum <= x && end < n)

        {

            // Игнорируем подмассивы с

            // отрицательная сумма, если х

            // положительный

            if (curr_sum <= 0 && x > 0)

            {

                start = end;

                curr_sum = 0;

            }

  

            curr_sum += arr[end++];

        }

  

        // Если текущая сумма становится

        // больше чем х.

        while (curr_sum > x && start < n)

        {

            // Обновление минимума

            // длина при необходимости

            if (end - start < min_len)

                min_len = end - start;

  

            // удаляем стартовые элементы

            curr_sum -= arr[start++];

        }

    }

    return min_len;

}

  

  
// Код драйвера

public static void main (String[] args)

{

    int arr1[] = {- 8, 1, 4, 2, -6};

    int x = 6;

    int n1 = arr1.length;

    int res1 = smallestSubWithSum(arr1, 

                                  n1, x);

    if(res1 == n1 + 1)

        System.out.println("Not possible");

    else            

        System.out.println (res1);

}
}

  
// Этот код предоставлен ajit

python3

# O (n) решение для поиска
# наименьший подмассив с суммой
# больше чем х

  
# Возвращает длину наименьшего
# подмассив с суммой большей
# чем х. Если нет
# подрешетка с заданной суммой,
# затем возвращает n + 1

def smallestSubWithSum(arr, n, x):

  

    # Инициализировать текущий

    # сумма и минимальная длина

    curr_sum = 0;

    min_len = n + 1;

  

    # Инициализировать запуск

    # и конечные индексы

    start = 0

    end = 0;

    while (end < n):

          

        # Продолжайте добавлять массив

        # элементов в то время как

        # текущая сумма

        # меньше чем х

        while (curr_sum <= x and end < n):

          

            # Игнорировать подмассивы с

            # отрицательная сумма, если х

            # положительный

            if (curr_sum <= 0 and x > 0):

                start = end;

                curr_sum = 0;

  

            curr_sum += arr[end];

            end += 1;

  

        # Если текущая сумма

        # становится больше, чем х.

        while (curr_sum > x and start < n):

            # Обновить минимум

            # длина при необходимости

            if (end - start < min_len):

                min_len = end - start;

  

            # удалить стартовые элементы

            curr_sum -= arr[start];

            start += 1;

              

    return min_len;

  
Код водителя

arr1 = [- 8, 1, 4, 2, -6];

x = 6;

n1 = len(arr1);

res1 = smallestSubWithSum(arr1, n1, x);

if(res1 == n1 + 1):

    print("Not possible");

else:

    print(res1);

  
# Этот код предоставлен mits

C #

// C # O (n) решение для
// найти наименьший подмассив
// с суммой больше чем x

using System;

  

class GFG

{

      
// Возвращает длину наименьшего
// подрешетка с большей суммой
// чем х. Если нет
// подрешетка с заданной суммой,
// затем возвращает n + 1

static int smallestSubWithSum(int []arr, 

                              int n, int x)

{

    // Инициализируем текущий

    // сумма и минимальная длина

    int curr_sum = 0, 

        min_len = n + 1;

  

    // Инициализация запуска

    // и конечные индексы

    int start = 0, end = 0;

    while (end < n)

    {

        // Продолжаем добавлять массив

        // элементы при текущем

        // сумма меньше чем х

        while (curr_sum <= x && 

               end < n)

        {

            // Игнорируем подмассивы с

            // отрицательная сумма, если х

            // положительный

            if (curr_sum <= 0 && x > 0)

            {

                start = end;

                curr_sum = 0;

            }

  

            curr_sum += arr[end++];

        }

  

        // Если текущая сумма становится

        // больше чем х.

        while (curr_sum > x && 

               start < n)

        {

            // Обновление минимума

            // длина при необходимости

            if (end - start < min_len)

                min_len = end - start;

  

            // удаляем стартовые элементы

            curr_sum -= arr[start++];

        }

    }

    return min_len;

}

  

  
// Код драйвера

static public void Main ()

{

    int []arr1 = {- 8, 1, 4, 2, -6};

    int x = 6;

    int n1 = arr1.Length;

    int res1 = smallestSubWithSum(arr1, 

                                  n1, x);

    if(res1 == n1 + 1)

        Console.WriteLine("Not possible");

    else    

        Console.WriteLine(res1);

}
}

  
// Этот код добавлен
// от akt_mit

PHP

<?php
// O (n) решение для поиска
// наименьший подмассив с суммой
// больше чем х

  
// Возвращает длину наименьшего
// подрешетка с большей суммой
// чем х. Если нет
// подрешетка с заданной суммой,
// затем возвращает n + 1

function smallestSubWithSum($arr

                            $n, $x)

{

    // Инициализируем текущий

    // сумма и минимальная длина

    $curr_sum = 0;

    $min_len = $n + 1;

  

    // Инициализация запуска

    // и конечные индексы

    $start = 0; $end = 0;

    while ($end < $n)

    {

        // Продолжаем добавлять массив

        // элементы while

        // текущая сумма

        // меньше чем х

        while ($curr_sum <= $x && 

               $end < $n)

        {

            // Игнорируем подмассивы с

            // отрицательная сумма, если х

            // положительный

            if ($curr_sum <= 0 && $x > 0)

            {

                $start = $end;

                $curr_sum = 0;

            }

  

            $curr_sum += $arr[$end++];

        }

  

        // Если текущая сумма

        // становится больше, чем х.

        while ($curr_sum > $x && 

               $start < $n)

        {

            // Обновление минимума

            // длина при необходимости

            if ($end - $start < $min_len)

                $min_len = $end - $start;

  

            // удаляем стартовые элементы

            $curr_sum -= $arr[$start++];

        }

    }

    return $min_len;

}

  

  
// Код драйвера

$arr1 = array(- 8, 1, 4, 2, -6);

$x = 6;

$n1 = sizeof($arr1);

$res1 = smallestSubWithSum($arr1

                           $n1, $x);

if($res1 == $n1+1) 

  

echo "Not possible\n" ;

else

  

echo $res1 , "\n";

  
// Этот код предоставлен ajit
?>


Выход:

3 

Спросил в: Facebook

Эта статья пополняемая Рахул Джейна. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Наименьший подмассив с суммой, превышающей заданное значение

0.00 (0%) 0 votes