തന്നിരിക്കുന്ന തുക ഉപയോഗിച്ച് സബ്‌റേ കണ്ടെത്തുക (നെഗറ്റീവ് നമ്പറുകൾ കൈകാര്യം ചെയ്യുന്നു)


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ആമസോൺ കൂപ്പൺ‌ഡ്യൂണിയ ദില്ലി GE ഹെൽത്ത്കെയർ വിവരം മൂൺഫ്രോഗ് ലാബുകൾ
അറേ ഹാഷ് സ്ലൈഡിംഗ് വിൻഡോ

“തന്നിരിക്കുന്ന തുക ഉപയോഗിച്ച് സബ്‌റേ കണ്ടെത്തുക (നെഗറ്റീവ് നമ്പറുകൾ കൈകാര്യം ചെയ്യുന്നു)” എന്ന പ്രശ്നം നിങ്ങൾക്ക് ഒരു നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു പൂർണ്ണസംഖ്യ ശ്രേണി, നെഗറ്റീവ് സംഖ്യകളും “സം” എന്ന് വിളിക്കുന്ന ഒരു സംഖ്യയും അടങ്ങിയിരിക്കുന്നു. പ്രശ്ന പ്രസ്താവന ഉപ-അറേ പ്രിന്റുചെയ്യാൻ ആവശ്യപ്പെടുന്നു, അത് “സം” എന്ന് വിളിക്കുന്ന ഒരു സംഖ്യയെ സംഗ്രഹിക്കുന്നു. ഞങ്ങളുടെ output ട്ട്‌പുട്ടിൽ ഒന്നിൽ കൂടുതൽ ഉപ-അറേ ഉണ്ടെങ്കിൽ, അവയിലേതെങ്കിലും പ്രിന്റുചെയ്യുക.

ഉദാഹരണം

തന്നിരിക്കുന്ന തുക ഉപയോഗിച്ച് സബ്‌റേ കണ്ടെത്തുക (നെഗറ്റീവ് നമ്പറുകൾ കൈകാര്യം ചെയ്യുന്നു)

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. ഗണം currentSum 0 ലേക്ക്.
  3. ശ്രേണിയിലൂടെ സഞ്ചരിക്കുക, ഞാൻ <n ആയിരിക്കുമ്പോൾ,
    1. കറന്റ്‌സമിന്റെയും അറേ എലമെന്റിന്റെയും മൂല്യം സംഗ്രഹിച്ച് കറന്റ്‌സമിൽ സംഭരിക്കുക.
    2. കറന്റ്സും തുകയ്ക്ക് തുല്യമാണോയെന്ന് പരിശോധിക്കുക.
      • ശരിയാണെങ്കിൽ, സൂചികയെ 0 മുതൽ i വരെ അച്ചടിച്ച് തകർക്കുക.
    3. നിലവിലെ സം-സം മൂല്യം മാപ്പിൽ ഉണ്ടോയെന്ന് പരിശോധിക്കുക.
      • ശരിയാണെങ്കിൽ സൂചികകൾ മാപ്പിന്റെ കറന്റ്സം മൂല്യമായി i ലേക്ക് പ്രിന്റുചെയ്‌ത് തകർക്കുക.
    4. തന്നിരിക്കുന്ന ഏതെങ്കിലും വ്യവസ്ഥ തൃപ്തികരമല്ലെങ്കിൽ, തന്നിരിക്കുന്ന തുകയിൽ ഞങ്ങൾ ഒന്നും കണ്ടെത്തിയില്ല.

വിശദീകരണം

തന്നിരിക്കുന്ന തുകയ്ക്ക് തുല്യമായ ഉപ-അറേ കണ്ടെത്താൻ ആവശ്യപ്പെടുന്ന ഒരു പ്രശ്ന പ്രസ്താവന ഞങ്ങൾക്ക് നൽകിയിട്ടുണ്ട്, ഒന്നിൽ കൂടുതൽ ഉപ-അറേകൾ ഉണ്ടെങ്കിൽ, അവയിലേതെങ്കിലും പ്രിന്റുചെയ്യുക. ഞങ്ങൾ ഉപയോഗിക്കാൻ പോകുന്നു ഹാഷ്‌മാപ്പ് ഞങ്ങൾ അതിന്റെ മൂല്യം സംഭരിക്കാൻ പോകുന്നു currentSum ന്റെ ഓരോ ഘടകങ്ങളും ചേർത്തതിന് ശേഷം നിബന്ധനകളൊന്നും തൃപ്തികരമല്ലെങ്കിൽ അതിന്റെ സൂചിക ശ്രേണി കറന്റ്സും (ഇത് 0 നേരത്തെ സമാരംഭിച്ചു).

നമുക്ക് ഒരു ഉദാഹരണം നോക്കാം:

ഉദാഹരണം

arr [] = {14, 1, -10, 20, 1}, തുക = 5

ചില നെഗറ്റീവ് സംഖ്യകളും ഒരു സംഖ്യയും അടങ്ങുന്ന ഒരു സംഖ്യ അറേ ഞങ്ങൾ നൽകി. തന്നിരിക്കുന്ന സംഖ്യ, തുക വരെ ചേർക്കുന്ന ഉപ-അറേ ഞങ്ങൾ കണ്ടെത്തണം. മുഴുവൻ അറേയിലും സഞ്ചരിക്കുമ്പോൾ നമ്മുടെ കറന്റ്സം നിലനിർത്തണം, ഇതാണ്, ഇത് സാധ്യമായ ഉപ-അറേ നൽകുന്നു.

i = 0, currentSum = 0

currentSum = currentSum + arr [i] => currentSum = 14, ഇപ്പോൾ നമ്മുടെ കറന്റ്സുമിൽ 14 ഉണ്ട്, തന്നിരിക്കുന്ന തുകയ്ക്ക് തുല്യമാണോ എന്ന് ഞങ്ങൾ പരിശോധിക്കും, അത് തെറ്റാണ്, തുടർന്ന് മാപ്പിൽ അടങ്ങിയിട്ടുണ്ടോ എന്ന് ഞങ്ങൾ പരിശോധിക്കും currentSum-sum അതായത് 5-14 = 5 എന്നതും തെറ്റാണ്. അതിനാൽ ഞങ്ങൾ അടുത്ത ഘടകത്തിലൂടെ പോകും. അതിനാൽ ഞങ്ങൾ കറന്റ്സും ഐയും മാപ്പിൽ ചേർക്കുന്നു.

i = 1, currentSum = 14

currentSum = currentSum + arr [i] => 14 + 1 = 15, currentSum = 15, ഇപ്പോൾ നമ്മുടെ കറന്റ്സുമിൽ 15 ഉണ്ട്, തന്നിരിക്കുന്ന തുകയ്ക്ക് തുല്യമാണോയെന്ന് ഞങ്ങൾ പരിശോധിക്കും, പക്ഷേ അത് തൃപ്തികരമല്ല, ഞങ്ങൾ പോകുകയാണെങ്കിൽ മാപ്പിൽ നിലവിലെ സം-സം അടങ്ങിയിരിക്കുന്നു, അത് 15-5-10 എന്നതും തെറ്റാണ്. അതിനാൽ ഞങ്ങൾ കറന്റ്സും ഐയും മാപ്പിൽ ചേർക്കുന്നു.

i = 2, currentSum = 15,

currentSum = currentSum + arr [i] => 15 + (-10), currentSum = 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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N) എവിടെ "N" അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം.

ബഹിരാകാശ സങ്കീർണ്ണത

O (N) എവിടെ "N" അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം.