ఇచ్చిన మొత్తంతో సబ్‌రేను కనుగొనండి (ప్రతికూల సంఖ్యలను నిర్వహిస్తుంది)


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది అమెజాన్ కూపన్ డునియా Delhivery GE హెల్త్ ఇన్ఫోఎడ్జ్ మూన్‌ఫ్రాగ్ ల్యాబ్స్
అర్రే హాష్ స్లైడింగ్ విండో

“ఇచ్చిన మొత్తంతో సబ్‌రేను కనుగొనండి (ప్రతికూల సంఖ్యలను నిర్వహిస్తుంది)” సమస్య మీకు ఇవ్వబడింది పూర్ణ సంఖ్య అమరిక, ప్రతికూల పూర్ణాంకాలు మరియు “మొత్తం” అని పిలువబడే సంఖ్యను కలిగి ఉంటుంది. సమస్య స్టేట్మెంట్ ఉప-శ్రేణిని ముద్రించమని అడుగుతుంది, ఇది ఇచ్చిన మొత్తం “మొత్తం” అని పిలువబడుతుంది. మా అవుట్‌పుట్‌గా ఒకటి కంటే ఎక్కువ ఉప-శ్రేణి ఉంటే, వాటిలో దేనినైనా ముద్రించండి.

ఉదాహరణ

ఇచ్చిన మొత్తంతో సబ్‌రేను కనుగొనండి (ప్రతికూల సంఖ్యలను నిర్వహిస్తుంది)

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. ప్రకటించండి a చిహ్నం.
  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 ఉంది, అది ఇచ్చిన మొత్తానికి సమానం కాదా అని తనిఖీ చేస్తాము, అది 5, మరియు అది తప్పు, అప్పుడు మ్యాప్‌లో ఉందో లేదో తనిఖీ చేస్తాము currentSum-sum అంటే 14-5 = 9 కూడా తప్పు. కాబట్టి మేము తదుపరి మూలకం ద్వారా వెళ్తాము. కాబట్టి మేము కరెంట్సమ్ మరియు ఐని మ్యాప్లో చేర్చుతాము.

i = 1, currentSum = 14

currentSum = currentSum + arr [i] => 14 + 1 = 15, currentSum = 15, ఇప్పుడు మన కరెంట్‌సమ్‌లో 15 ఉన్నాయి, అది ఇచ్చిన మొత్తానికి సమానంగా ఉందో లేదో తనిఖీ చేస్తాము కాని అది సంతృప్తి చెందలేదు, మేము ఉంటే మ్యాప్‌లో ప్రస్తుతసమ్-మొత్తం 15-5-10 కూడా ఉంది. కాబట్టి మేము కరెంట్సమ్ మరియు ఐని మ్యాప్లో చేర్చుతాము.

i = 2, కరెంట్‌సమ్ = 15,

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

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై) (ఇక్కడ  “ఎన్” శ్రేణిలోని మూలకాల సంఖ్య.

అంతరిక్ష సంక్లిష్టత

పై) (ఇక్కడ  “ఎన్” శ్రేణిలోని మూలకాల సంఖ్య.