Рубрики

Найти подмассив с заданной суммой | Набор 1 (неотрицательные числа)

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

Примеры :

Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33
Ouptut: Sum found between indexes 2 and 4

Input: arr[] = {1, 4, 0, 0, 3, 10, 5}, sum = 7
Ouptut: Sum found between indexes 1 and 4

Input: arr[] = {1, 4}, sum = 0
Output: No subarray found

Может быть более одного подмассива с суммой в качестве заданной суммы. Следующие решения печатают первый такой подмассив.

Способ 1 (простой)
Простое решение состоит в том, чтобы рассмотреть все подмассивы один за другим и проверить сумму каждого подмассива. Следующая программа реализует простое решение. Мы запускаем два цикла: внешний цикл выбирает начальную точку i, а внутренний цикл пробует все подмассивы, начиная с i.

Ниже приводится реализация вышеуказанного подхода.

C ++

/ * Простая программа для печати подмассива
с суммой как заданная сумма * /
#include <bits/stdc++.h>

using namespace std; 

  
/ * Возвращает true, если есть подмассив
arr [] с суммой, равной 'sum' в противном случае
возвращает ложь Также печатает результат * /

int subArraySum(int arr[], int n, int sum) 

    int curr_sum, i, j; 

  

    // Выберите начальную точку

    for (i = 0; i < n; i++) 

    

        curr_sum = arr[i]; 

  

        // пробуем все подмассивы, начинающиеся с 'i'

        for (j = i + 1; j <= n; j++) 

        

            if (curr_sum == sum) 

            

                cout << "Sum found between indexes " 

                     << i << " and " << j - 1; 

                return 1; 

            

            if (curr_sum > sum || j == n) 

                break

        curr_sum = curr_sum + arr[j]; 

        

    

  

    cout << "No subarray found"

    return 0; 

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

int main() 

    int arr[] = {15, 2, 4, 8, 9, 5, 10, 23}; 

    int n = sizeof(arr) / sizeof(arr[0]); 

    int sum = 23; 

    subArraySum(arr, n, sum); 

    return 0; 

  
// Этот код добавлен
// ратбхупендра

С

/ * Простая программа для печати подмассива с суммой в виде заданной суммы * /
#include<stdio.h>

  
/ * Возвращает true, если есть подмассив arr [] с суммой, равной 'sum'

   в противном случае возвращает false. Также печатает результат * /

int subArraySum(int arr[], int n, int sum)

{

    int curr_sum, i, j;

  

    // Выберите начальную точку

    for (i = 0; i < n; i++)

    {

        curr_sum = arr[i];

  

        // пробуем все подмассивы, начинающиеся с 'i'

        for (j = i+1; j <= n; j++)

        {

            if (curr_sum == sum)

            {

                printf ("Sum found between indexes %d and %d", i, j-1);

                return 1;

            }

            if (curr_sum > sum || j == n)

                break;

           curr_sum = curr_sum + arr[j];

        }

    }

  

    printf("No subarray found");

    return 0;

}

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

int main()

{

    int arr[] = {15, 2, 4, 8, 9, 5, 10, 23};

    int n = sizeof(arr)/sizeof(arr[0]);

    int sum = 23;

    subArraySum(arr, n, sum);

    return 0;

}

Джава

class SubarraySum 

{

    / * Возвращает true, если есть подмассив arr [] с суммой, равной

       иначе sum возвращает false. Также печатает результат * /

    int subArraySum(int arr[], int n, int sum) 

    {

        int curr_sum, i, j;

  

        // Выберите начальную точку

        for (i = 0; i < n; i++) 

        {

            curr_sum = arr[i];

  

            // пробуем все подмассивы, начинающиеся с 'i'

            for (j = i + 1; j <= n; j++) 

            {

                if (curr_sum == sum) 

                {

                    int p = j - 1;

                    System.out.println("Sum found between indexes " + i

                            + " and " + p);

                    return 1;

                }

                if (curr_sum > sum || j == n)

                    break;

                curr_sum = curr_sum + arr[j];

            }

        }

  

        System.out.println("No subarray found");

        return 0;

    }

  

    public static void main(String[] args) 

    {

        SubarraySum arraysum = new SubarraySum();

        int arr[] = {15, 2, 4, 8, 9, 5, 10, 23};

        int n = arr.length;

        int sum = 23;

        arraysum.subArraySum(arr, n, sum);

    }

}

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

python3

# Возвращает true, если
# есть подмассив
№ обр [с суммой
# равно сумме
# в противном случае возвращается
# ложный. Также печатает
# результат

def subArraySum(arr, n, sum):

      

    # Выберите начало

    # точка

    for i in range(n):

        curr_sum = arr[i]

      

        # попробуйте все подмассивы

        # начинающийся с 'i'

        j = i+1

        while j <= n:

          

            if curr_sum == sum:

                print ("Sum found between")

                print("indexes %d and %d"%( i, j-1))

                  

                return 1

                  

            if curr_sum > sum or j == n:

                break

              

            curr_sum = curr_sum + arr[j]

            j += 1

  

    print ("No subarray found")

    return 0

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

arr = [15, 2, 4, 8, 9, 5, 10, 23]

n = len(arr)

sum = 23

  

subArraySum(arr, n, sum)

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

C #

// C # код для поиска подмассива
// с заданной суммой

using System;

  

class GFG 

{

    // Возвращает true, если есть

    // подмассив arr [] с суммой

    // равно 'sum' в противном случае возвращает

    // ложный. Также печатает результат

    int subArraySum(int []arr, int n, 

                               int sum) 

    {

        int curr_sum, i, j;

  

        // Выберите начальную точку

        for (i = 0; i < n; i++) 

        {

            curr_sum = arr[i];

  

            // попробовать все подмассивы

            // начинаем с 'i'

            for (j = i + 1; j <= n; j++) 

            {

                if (curr_sum == sum) 

                {

                    int p = j - 1;

                    Console.Write("Sum found between "

                                        "indexes " + i + 

                                           " and " + p);

                    return 1;

                }

                if (curr_sum > sum || j == n)

                    break;

                curr_sum = curr_sum + arr[j];

            }

        }

  

        Console.Write("No subarray found");

        return 0;

    }

  

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

    public static void Main() 

    {

        GFG arraysum = new GFG();

        int []arr = {15, 2, 4, 8, 9, 5, 10, 23};

        int n = arr.Length;

        int sum = 23;

        arraysum.subArraySum(arr, n, sum);

    }

}

  
// Этот код был добавлен
// нитин митталь

PHP

<?php
// Простая программа для печати подмассива
// с суммой как заданная сумма

  
/ * Возвращает true, если есть

   подмассив arr [] с

   сумма равна сумме

   в противном случае возвращает false.

   Также печатает результат * /

function subArraySum($arr, $n, $sum)

{

    $curr_sum; $i; $j;

  

    // Выберите начальную точку

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

    {

        $curr_sum = $arr[$i];

  

        // попробовать все подмассивы

        // начинаем с 'i'

        for ($j = $i + 1; $j <= $n; $j++)

        {

            if ($curr_sum == $sum)

            {

                echo "Sum found between indexes " 

                      ,$i ," and " ,$j-1 ;

                return 1;

            }

            if ($curr_sum > $sum || $j == $n)

                break;

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

        }

    }

  

    echo "No subarray found";

    return 0;

}

  

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

    $arr= array(15, 2, 4, 8, 9, 5, 10, 23);

    $n = sizeof($arr);

    $sum = 23;

    subArraySum($arr, $n, $sum);

    return 0;

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


Выход :

Sum found between indexes 1 and 4

Сложность времени: O (n ^ 2) в худшем случае.

Метод 2 (Эффективный)
Инициализируйте переменную curr_sum в качестве первого элемента. curr_sum указывает сумму текущего подмассива. Начните со второго элемента и добавьте все элементы один за другим в curr_sum. Если curr_sum становится равным сумме, выведите решение. Если curr_sum превышает сумму, то удаляются конечные элементы, а curr_sum больше, чем сумма.

Ниже приводится реализация вышеуказанного подхода.

C ++

/ * Эффективная программа для печати
подрешетка с суммой как заданная сумма * /
#include <iostream>

using namespace std;

  
/ * Возвращает true, если есть подмассив
arr [] с суммой, равной 'sum' в противном случае
возвращает ложь Также печатает результат * /

int subArraySum(int arr[], int n, int sum)

{

    / * Инициализировать curr_sum как значение

    первый элемент и начальная точка как 0 * /

    int curr_sum = arr[0], start = 0, i;

  

    / * Добавить элементы один за другим в curr_sum и

    если curr_sum превышает сумму,

    затем удалить стартовый элемент * /

    for (i = 1; i <= n; i++)

    {

        // Если curr_sum превышает сумму,

        // затем удаляем начальные элементы

        while (curr_sum > sum && start < i - 1)

        {

            curr_sum = curr_sum - arr[start];

            start++;

        }

  

        // Если curr_sum становится равным sum,

        // затем возвращаем true

        if (curr_sum == sum)

        

            cout << "Sum found between indexes " 

                 << start << " and " << i - 1;

            return 1;

        }

  

        // Добавить этот элемент в curr_sum

        if (i < n)

        curr_sum = curr_sum + arr[i];

    }

  

    // Если мы доберемся сюда, то нет подмассива

    cout << "No subarray found";

    return 0;

}

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

int main()

{

    int arr[] = {15, 2, 4, 8, 9, 5, 10, 23};

    int n = sizeof(arr) / sizeof(arr[0]);

    int sum = 23;

    subArraySum(arr, n, sum);

    return 0;

}

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

С

/ * Эффективная программа для печати подмассива с суммой в виде заданной суммы * /
#include<stdio.h>

  
/ * Возвращает true, если есть подмассив arr [] с суммой, равной 'sum'

   в противном случае возвращает false. Также печатает результат * /

int subArraySum(int arr[], int n, int sum)

{

    / * Инициализировать curr_sum как значение первого элемента

       и начальная точка как 0 * /

    int curr_sum = arr[0], start = 0, i;

  

    / * Добавить элементы один за другим в curr_sum и, если curr_sum превышает

       сумма, затем удалить начальный элемент * /

    for (i = 1; i <= n; i++)

    {

        // Если curr_sum превышает сумму, то удаляем начальные элементы

        while (curr_sum > sum && start < i-1)

        {

            curr_sum = curr_sum - arr[start];

            start++;

        }

  

        // Если curr_sum становится равным sum, вернуть true

        if (curr_sum == sum)

        {

            printf ("Sum found between indexes %d and %d", start, i-1);

            return 1;

        }

  

        // Добавить этот элемент в curr_sum

        if (i < n)

          curr_sum = curr_sum + arr[i];

    }

  

    // Если мы доберемся сюда, то нет подмассива

    printf("No subarray found");

    return 0;

}

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

int main()

{

    int arr[] = {15, 2, 4, 8, 9, 5, 10, 23};

    int n = sizeof(arr)/sizeof(arr[0]);

    int sum = 23;

    subArraySum(arr, n, sum);

    return 0;

}

Джава

class SubarraySum

{

    / * Возвращает true, если есть подмассив arr [] с суммой, равной

       иначе sum возвращает false. Также печатает результат * /

    int subArraySum(int arr[], int n, int sum) 

    {

        int curr_sum = arr[0], start = 0, i;

  

        // Выберите начальную точку

        for (i = 1; i <= n; i++) 

        {

            // Если curr_sum превышает сумму, то удаляем начальные элементы

            while (curr_sum > sum && start < i-1)

            {

                curr_sum = curr_sum - arr[start];

                start++;

            }

              

            // Если curr_sum становится равным sum, вернуть true

            if (curr_sum == sum) 

            {

                int p = i-1;

                System.out.println("Sum found between indexes " + start

                        + " and " + p);

                return 1;

            }

              

            // Добавить этот элемент в curr_sum

            if (i < n)

            curr_sum = curr_sum + arr[i];

              

        }

  

        System.out.println("No subarray found");

        return 0;

    }

  

    public static void main(String[] args) 

    {

        SubarraySum arraysum = new SubarraySum();

        int arr[] = {15, 2, 4, 8, 9, 5, 10, 23};

        int n = arr.length;

        int sum = 23;

        arraysum.subArraySum(arr, n, sum);

    }

}

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

python3

# Эффективная программа
# для печати подмассива
# с суммой как заданная сумма

  
# Возвращает true, если
# есть подмассив
№ обр [с суммой
# равно сумме
# в противном случае возвращается
# ложный. Также печатает
# результат.

def subArraySum(arr, n, sum):

      

    # Инициализировать curr_sum как

    # значение первого элемента

    # и начальная точка как 0

    curr_sum = arr[0]

    start = 0

  

    # Добавить элементы по одному

    # один к curr_sum и

    # если curr_sum превышает

    # сумма, затем удалить

    # начальный элемент

    i = 1

    while i <= n:

          

        # Если curr_sum превышает

        # сумма, затем удалить

        # стартовые элементы

        while curr_sum > sum and start < i-1:

          

            curr_sum = curr_sum - arr[start]

            start += 1

              

        # Если curr_sum становится

        # равно сумме, тогда

        # верните true

        if curr_sum == sum:

            print ("Sum found between indexes")

            print ("%d and %d"%(start, i-1))

            return 1

  

        # Добавить этот элемент

        # до curr_sum

        if i < n:

            curr_sum = curr_sum + arr[i]

        i += 1

  

    # Если мы достигнем здесь,

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

    print ("No subarray found")

    return 0

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

arr = [15, 2, 4, 8, 9, 5, 10, 23]

n = len(arr)

sum = 23

  

subArraySum(arr, n, sum)

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

C #

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

using System;

  

class GFG 

{

      

    // Возвращает true, если

    // есть подмассив

    // arr [] с суммой, равной

    // иначе sum возвращает false.

    // Также печатает результат

    int subArraySum(int[] arr, int n, 

                               int sum) 

    {

        int curr_sum = arr[0], 

                 start = 0, i;

  

        // Выберите начальную точку

        for (i = 1; i <= n; i++) 

        {

            // Если curr_sum превышает

            // сумма, затем удалить

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

            while (curr_sum > sum && 

                   start < i - 1)

            {

                curr_sum = curr_sum - 

                           arr[start];

                start++;

            }

              

            // Если curr_sum становится равным

            // сумма, затем возвращаем true

            if (curr_sum == sum) 

            {

                int p = i-1;

                Console.WriteLine("Sum found between " +

                                     "indexes " + start+ 

                                           " and " + p);

                return 1;

            }

              

            // Добавить этот элемент в curr_sum

            if (i < n)

            curr_sum = curr_sum + arr[i];

              

        }

        Console.WriteLine("No subarray found");

        return 0;

    }

  

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

    public static void Main() 

    {

        GFG arraysum = new GFG();

        int[] arr =new int[] {15, 2, 4, 8, 

                              9, 5, 10, 23};

        int n = arr.Length;

        int sum = 23;

        arraysum.subArraySum(arr, n, sum);

    }

}

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

PHP

<?php
/ * Эффективная программа для печати
подрешетка с суммой как заданная сумма * /

  
/ * Возвращает true, если есть
подмассив arr [] с равной суммой
в противном случае возвращается «ложь».
Также печатает результат * /

function subArraySum($arr, $n, $sum)

{

    / * Инициализировать curr_sum как

    значение первого элемента

    и начальная точка как 0 * /

    $curr_sum = $arr[0]; 

    $start = 0; $i;

  

    / * Добавить элементы один за другим в

    curr_sum и если curr_sum

    превышает сумму, затем удалите

    начальный элемент * /

    for ($i = 1; $i <= $n; $i++)

    {

        // Если curr_sum превышает сумму,

        // затем удаляем начальные элементы

        while ($curr_sum > $sum and 

               $start < $i - 1)

        {

            $curr_sum = $curr_sum

                        $arr[$start];

            $start++;

        }

  

        // Если curr_sum становится равным

        // суммируем, затем возвращаем true

        if ($curr_sum == $sum)

        {

            echo "Sum found between indexes" ,

                             " ", $start, " "

                           "and "," ", $i - 1;

            return 1;

        }

  

        // Добавить этот элемент

        // до curr_sum

        if ($i < $n)

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

    }

  

    // Если мы достигнем здесь,

    // тогда нет подмассива

    echo "No subarray found";

    return 0;

}

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

$arr = array(15, 2, 4, 8, 

              9, 5, 10, 23);

$n = count($arr);

$sum = 23;

subArraySum($arr, $n, $sum);

  
// Этот код был
// предоставлено anuj_67.
?>


Выход :

Sum found between indexes 1 and 4

Временная сложность метода 2 выглядит больше, чем O (n), но если мы более внимательно посмотрим на программу, то мы можем выяснить, что временная сложность равна O (n). Мы можем доказать это, посчитав количество операций, выполненных над каждым элементом arr [] в худшем случае. На каждом элементе выполняется не более 2 операций: (a) элемент добавляется в curr_sum (b) элемент вычитается из curr_sum. Таким образом, верхняя граница количества операций равна 2n, что равно O (n).

Вышеупомянутое решение не обрабатывает отрицательные числа. Мы можем использовать хеширование для обработки отрицательных чисел. Смотрите ниже набор 2.

Найти подмассив с заданной суммой | Набор 2 (Обрабатывает отрицательные числа)

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

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

Найти подмассив с заданной суммой | Набор 1 (неотрицательные числа)

0.00 (0%) 0 votes