આપેલ રકમ સાથે સબઅરેરે (નકારાત્મક નંબરો સંભાળે છે) શોધો  


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એમેઝોન કુપનદુનિયા દિલ્હીવારી જીઇ હેલ્થકેર માહિતી એડજ મૂનફ્રોગ લેબ્સ
અરે હેશ બારણું વિંડો

સમસ્યા "આપેલ રકમ સાથેના સબઅરરે શોધો (નેગેટિવ નંબર્સ હેન્ડલ્સ)" જણાવે છે કે તમને એ પૂર્ણાંક એરે, નકારાત્મક પૂર્ણાંકો અને "સરવાળો" તરીકે ઓળખાતી સંખ્યા ધરાવતા હોય છે. સમસ્યાનું નિવેદન પેટા-એરે છાપવાનું કહે છે, જે આપેલ નંબરને સરવાળો કહે છે, જેનો સરવાળો છે જો અમારા આઉટપુટ તરીકે એક કરતા વધુ પેટા-એરે હાજર હોય, તો તેમાંથી કોઈપણ છાપો.

ઉદાહરણ  

આપેલ રકમ સાથે સબઅરેરે (નકારાત્મક નંબરો સંભાળે છે) શોધોપિન

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. એરેને પસાર કરો, જ્યારે હું <એન,
    1. કરંટસમ અને એરે એલિમેન્ટના મૂલ્યનો સરવાળો કરે છે અને તેને કરન્ટસમમાં સ્ટોર કરે છે.
    2. કરન્ટસમ સરવાળો થાય તે તપાસો.
      • જો ખરું હોય તો, પછી અનુક્રમણિકાને 0 થી i તરીકે છાપો અને વિરામ કરો.
    3. નકશામાં વર્તમાન વર્તમાન રકમનો સરવાળો છે કે કેમ તે તપાસો.
      • જો સાચું હોય તો, નકશાના વર્તમાનસમ મૂલ્ય તરીકે અનુક્રમણિકા છાપો અને ભંગ કરો.
    4. જો આપેલ કોઈપણ શરત સંતોષતી નથી, તો તેનો અર્થ એ કે આપેલ રકમ સાથે અમને કંઈ મળ્યું નથી.

સમજૂતી

અમને એક સમસ્યાનું નિવેદન આપવામાં આવ્યું છે જે આપેલ રકમની રકમનો પેટા-એરે શોધવા માટે પૂછે છે અને જો ત્યાં એકથી વધુ પેટા-એરે મળે છે, તો તેમાંથી કોઈપણ છાપો. આપણે વાપરવા જઈ રહ્યા છીએ હેશમેપ અને આપણે ની વેલ્યુ સંગ્રહવા જઈશું કરંટસમ અને તેનું અનુક્રમણિકા જો દરેક તત્વ ઉમેર્યા પછી કોઈ પણ સ્થિતિ સંતોષાય નહીં એરે અને કરન્ટસમ (જે 0 અગાઉ શરૂ કરવામાં આવી હતી).

આ પણ જુઓ
0s અને 1s ની સમાન સંખ્યા સાથેનો મોટો સબઅરે

ચાલો આપણે એક ઉદાહરણ ધ્યાનમાં લઈએ:

ઉદાહરણ

એરે [] = {14, 1, -10, 20, 1}, સરવાળો = 5

અમે પૂર્ણાંક એરે આપી છે જેમાં કેટલાક નકારાત્મક પૂર્ણાંકો અને સંખ્યા રકમ શામેલ છે. આપણે પેટા-એરે શોધવા પડશે જે આપેલ સંખ્યા, રકમનો ઉમેરો કરશે. આખા એરેને ટ્ર traવર્સ કરતી વખતે આપણે આપણો કરંટસમ જાળવવો જોઈએ, આ તે છે જે આપણને સંભવિત સબ-એરે આપે છે.

i = 0, કરન્ટસમ = 0

કરંટસમ = કરંટસમ + એઆરઆર [i] => કરન્ટસમ = ૧,, હવે આપણી વર્તમાન કરંટમાં ૧ in છે, અમે તપાસ કરીશું કે આપેલ રકમ જે is છે તે બરાબર છે કે નહીં, અને તે ખોટું છે, તો અમે તપાસ કરીશું કે નકશામાં સમાવિષ્ટ છે કે નહીં કરન્ટસમ-સમ એટલે કે 14-14 = 5 એ પણ ખોટું છે. તેથી આપણે આગળના તત્વમાંથી પસાર થઈશું. તેથી અમે નકશામાં કરન્ટસમ અને હું ઉમેરીશું.

i = 1, કરન્ટસમ = 14

કરન્ટસમ = કરંટસમ + એઆરઆર [i] => 14 + 1 = 15, કરન્ટસમ = 15, હવે આપણી વર્તમાન કરંટમાં 15 છે, અમે તપાસ કરીશું કે આપેલ રકમની બરાબર છે કે નહીં પરંતુ તે સંતોષ નથી કરતું, આપણે જો નકશામાં વર્તમાનનો સરવાળો છે જે 15-5-10 છે તે પણ ખોટું છે. તેથી અમે નકશામાં કરન્ટસમ અને હું ઉમેરીશું.

i = 2, વર્તમાનસમ = 15,

કરંટસમ = કરંટસમ + એઆરઆર [i] => 15 + (-10), કરન્ટસમ = 5, હવે આપણી વર્તમાન કરંટમાં 15 છે, અમે તપાસ કરીશું કે આપેલ રકમ જે 5 છે તે બરાબર છે કે નહીં, અને અમે જોયું કે સ્થિતિ સંતુષ્ટ છે, મતલબ કે આપણને આપણું આઉટપુટ મળી ગયું છે, ત્યારબાદ આપણે સબએરેરી 0 થી i ના અનુક્રમણિકા છાપીએ.

કોડ  

સી ++ કોડ આપેલ રકમ સાથે સબરા્રે શોધવા માટે (નેગેટિવ નંબર્સ સંભાળે છે)

#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

જટિલતા વિશ્લેષણ  

સમય જટિલતા

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે.

આ પણ જુઓ
નિવેશ સortર્ટ

અવકાશ જટિલતા

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે.