Пронађи подред са задатим збиром (обрађује негативне бројеве)  


Ниво тешкоће Средњи
Често питани у амазонка ЦоупонДуниа Делхивери ГЕ Хеалтхцаре ИнфоЕдге Моонфрог Лабс
Ред Хасх Клизни прозор

Проблем „Пронађи подред са задатим збројем (обрађује негативне бројеве)“ наводи да сте добили цео број поредак, који садржи негативне целобројне бројеве и број који се назива „збир“. Изјава о проблему тражи испис под-низа, који сажима дати број који се назива „збир“. Ако је више од једног под-низа присутно као наш излаз, одштампајте било који од њих.

Пример  

Пронађи подред са задатим збиром (обрађује негативне бројеве)Пин

arr[] = {2,4,-2,3,1}
sum = 1
Sum found between index 2 to index 3
arr[] = {12,10,-20,30,1}
sum = 20
Sum found between index 1 to index 3
arr[] = {2,4,-2,3,1}
sum = -1
No such sub-array exists.

Алгоритам  

  1. Изјавите а Мапа.
  2. Сет цуррентСум да КСНУМКС.
  3. Пређите низ, док је и <н,
    1. Збира вредност цуррентСум и елемента низа и чува је у цуррентСум.
    2. Проверите да ли је цуррентСум једнак збиру.
      • Ако је тачно, испишите индекс као 0 до и и преломите.
    3. Проверите да ли карта садржи вредност цуррентСум-сум.
      • Ако је тачно, испишите индексе као тренутну вредност мапе на и и разбијте.
    4. Ако било који од задатих услова не задовољава, значи да нисмо пронашли ништа са датом сумом.

Објашњење

Добили смо изјаву о проблему која тражи да сазнамо под-низ који сажима дати зброј и ако је пронађено више под-низова, одштампајте било који од њих. Користићемо ХасхМап и чуваћемо вредност цуррентСум и његов индекс ако ниједан од услова није задовољен након сабирања сваког елемента поредак и цуррентСум (који је раније иницијализован као 0).

Види такође
Највећи подред са једнаким бројем 0 и 1

Размотримо пример:

Пример

арр [] = {14, 1, -10, 20, 1}, сума = 5

Дали смо целобројни низ који садржи и неке негативне целобројне вредности и збир бројева. Морамо да сазнамо под-низ који се збраја са датим бројем, збиром. Док обилазимо читав низ, требали бисмо одржавати свој цуррентСум, то нам даје могући под-низ.

и = 0, цуррентСум = 0

цуррентСум = цуррентСум + арр [и] => цуррентСум = 14, сада у нашем цуррентСум имамо 14, проверићемо да ли је једнак датој суми која је 5, а то је нетачно, онда ћемо проверити да ли карта садржи цуррентСум-сум што значи да је 14-5 = 9 такође нетачно. Тако ћемо проћи кроз следећи елемент. Дакле, додајемо цуррентСум и и на мапу.

и = 1, цуррентСум = 14

цуррентСум = цуррентСум + арр [и] => 14 + 1 = 15, цуррентСум = 15, сада имамо 15 у нашој цуррентСум, проверићемо да ли је једнак датој суми, али није задовољен, ићи ћемо на иф мапа садржи цуррентСум-сум који је 15-5-10 је такође нетачна. Дакле, додајемо цуррентСум и и на мапу.

и = 2, тренутна сума = 15,

цуррентСум = цуррентСум + арр [и] => 15 + (-10), цуррентСум = 5, сада имамо 15 у нашој цуррентСум, проверићемо да ли је једнак датој суми која је 5, и утврдили смо да је услов је задовољан, значи да смо добили излаз, а затим ћемо исписати индексе подниза 0 до и.

код  

Ц ++ код за проналажење подреда са задатом сумом (обрађује негативне бројеве)

#include<iostream>
#include<unordered_map>

using namespace std;

void getSubArray(int arr[], int n, int sum)
{
    unordered_map<int, int> map;
    int currentSum = 0;
    for (int i = 0; i < n; i++)
    {
        currentSum = currentSum + arr[i];
        if (currentSum == sum)
        {
            cout << "Sum found between index "<< 0 << " to index " << i << endl;
            return;
        }
        if (map.find(currentSum - sum) != map.end())
        {
            cout << "Sum found between index "<< map[currentSum - sum] + 1 << " to index " << i << endl;
            return;
        }
        map[currentSum] = i;
    }
    cout << " No such sub-array exists ";
}
int main()
{
    int arr[] = {14, 1, -10, 20, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    int sum = 5;
    getSubArray(arr, n, sum);
    return 0;
}
Sum found between index 0 to index 2

Јава код за проналажење низа са задатом сумом (обрађује негативне бројеве)

import java.util.HashMap;

class printSubArraywithGivenSum
{
    public static void getSubArray(int[] arr, int n, int sum)
    {
        int currentSum = 0;
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < n; i++)
        {
            currentSum = currentSum + arr[i];
            if (currentSum - sum == 0)
            {
                System.out.println("Sum found between index "+ 0 + " to index " + i);
                return;
            }
            if (map.containsKey(currentSum - sum))
            {
                int val=map.get(currentSum-sum)+1;
                System.out.println("Sum found between index "+ val+" to index " + i);
                return;
            }
            map.put(currentSum, i);
        }
        System.out.println("No such sub-array exists");
    }
    public static void main(String[] args)
    {
        int[] arr = {14, 1, -10, -20, 2};
        int n = arr.length;
        int sum = 5;
        getSubArray(arr, n, sum);
    }
}
Sum found between index 0 to index 2

Анализа сложености  

Сложеност времена

НА) где "Н" је број елемената у низу.

Види такође
Сортирање уметања

Сложеност простора

НА) где "Н" је број елемената у низу.