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


Ниво на тешкотија Медиум
Често прашувано во Амазон КупонДунија Деливерија ГЕ здравство ИнфоЕџ Лаборатории за месечина
Низа Хаш Лизгачки прозорец

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

пример

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

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. Намести струјаСума да 0.
  3. Преминете низ низата, додека јас <n,
    1. Ја сумира вредноста на тековниот Збир и елементот на низата и чувајте ги на тековната сума.
    2. Проверете дали сегашната сума е еднаква на збирот.
      • Ако е точно, тогаш отпечатете го индексот како 0 до i и скршете.
    3. Проверете дали мапата ја содржи вредноста струја Збир-збир.
      • Ако е точно, отпечатете ги индексите како моментална сума на мапата на i и скршете.
    4. Ако некој од дадениот услов не задоволува, тоа значи дека не најдовме ништо со дадената сума.

Објаснување

Дадена ни е изјава за проблем што бара да ја откриеме под-низата што се собира до дадената сума и ако има повеќе од една пронајдена под-низа, тогаш испечатете која било од нив. Е користиме HashMap и ние ќе ја зачуваме вредноста на струјаСума и неговиот индекс ако ниту еден од условите не е исполнет по собирањето на секој елемент од низа и currentSum (што беше иницијализирано како 0 порано).

Да разгледаме пример:

пример

arr [] = {14, 1, -10, 20, 1}, збир = 5

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

i = 0, currentSum = 0

currentSum = currentSum + arr [i] => currentSum = 14, сега имаме 14 во нашето currentSum, ќе провериме дали е еднаква на дадената сума што е 5, а тоа е погрешно, тогаш ќе провериме дали мапата го содржи збир-збир што значи 14-5 = 9 исто така е лажен. Значи, ќе го поминеме следниот елемент. Значи, ги додаваме currentSum и i во картата.

i = 1, currentSum = 14

currentSum = currentSum + arr [i] => 14 + 1 = 15, currentSum = 15, сега имаме 15 во нашето currentSum, ќе провериме дали е еднаква на дадената сума, но не е задоволна, ќе се обидеме ако мапата содржи тековен збир што е 15-5-10 е исто така неточен. Значи, ги додаваме currentSum и i во картата.

i = 2, струја Збир = 15,

currentSum = currentSum + arr [i] => 15 + (-10), currentSum = 5, сега имаме 15 во нашето currentSum, ќе провериме дали е еднаква на дадената сума што е 5, и откривме дека состојбата е задоволен, значи дека го добивме нашиот излез, тогаш ќе ги отпечатиме индексите на подредот 0 до i.

Код

C ++ код за наоѓање на под-низа со дадена сума (се справува со негативни броеви)

#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

Java код за наоѓање на под-низа со дадена сума (се справува со негативни броеви)

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

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

Временска комплексност

НА) каде „Н“ е бројот на елементи во низата.

Комплексноста на просторот

НА) каде „Н“ е бројот на елементи во низата.