పొడవైన సుబారే 1 సె లెక్కింపు 0 సెకన్ల కన్నా ఎక్కువ


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది యాక్సెంచర్ అమెజాన్ డిఇ షా శామ్సంగ్
అర్రే హాష్

మేము ఒక ఇచ్చాము అమరిక పూర్ణాంకాల. శ్రేణి 1 మరియు 0 లను మాత్రమే కలిగి ఉంటుంది. 1 యొక్క అంకెల పరిమాణాన్ని కలిగి ఉన్న ఉప-శ్రేణి యొక్క పొడవును ఉప-శ్రేణిలో 0 యొక్క గణన కంటే ఒకటి మాత్రమే అని సమస్య స్టేట్మెంట్ అడుగుతుంది.

ఉదాహరణ

ఇన్పుట్:

arr [] = {1,0,1,1,0,0,0}

అవుట్పుట్:

5

వివరణ:

0 నుండి 4 సూచిక వరకు, {1, 0, 1, 1, 0}, మూడు ఉన్నాయి 1 మరియు రెండు 0 లు. 1 ల కంటే 0 యొక్క మరో గణన.

ఇన్పుట్:

arr [] = {1,0,1,0,0}

అవుట్పుట్:

3

వివరణ:

0 నుండి 2 సూచిక వరకు, {1, 0, 1}, రెండు 1 లు మరియు ఒక 0 లు ఉన్నాయి. 1 ల కంటే 0 యొక్క మరో గణన.

అల్గారిథం

  1. మ్యాప్‌ను ప్రకటించండి.
  2. మొత్తం మరియు అవుట్పుట్ పొడవును 0 కు సెట్ చేయండి.
  3. శ్రేణిని దాటండి, i = 0 నుండి i <n వరకు.
    1. నిజమైనది అయితే arr [i] 0 కి సమానంగా ఉందో లేదో తనిఖీ చేసి, ఆపై మొత్తానికి -1 జోడించండి.
    2. మొత్తానికి +1 జోడించండి.
    3. ఉంటే తనిఖీ చేయండి మొత్తం సమానం 1 కు, ఆపై అవుట్పుట్ పొడవు విలువను 1 పెంచండి.
    4. లేకపోతే, మ్యాప్‌లో మొత్తం ఉంటే మొత్తాన్ని కలిగి ఉండలేదా అని తనిఖీ చేయండి.
    5. మ్యాప్‌లో (మొత్తం -1) ఉందో లేదో తనిఖీ చేయండి.
    6. అవుట్పుట్ పొడవు ఐ-ఇండెక్స్ కంటే తక్కువగా ఉంటే (మ్యాప్‌లో మొత్తం విలువ).
      1. నిజమైతే, అవుట్‌పుట్ పొడవును ఐ-ఇండెక్స్‌కు నవీకరించండి.
  4. అవుట్పుట్ పొడవును తిరిగి ఇవ్వండి.

వివరణ

మేము ఒక ప్రకటిస్తాము చిహ్నం. ఆ మ్యాప్‌లో, షరతు సంతృప్తి చెందితే, మొత్తం విలువ మరియు సూచిక యొక్క ప్రస్తుత విలువను నిల్వ చేయబోతున్నాం. రెండు వేరియబుల్స్ తీసుకోండి మరియు మొత్తాన్ని 0 గా మరియు అవుట్పుట్ పొడవును 0 గా సెట్ చేయండి. శ్రేణిని దాటుతున్నప్పుడు, మేము శ్రేణి యొక్క ప్రతి మూలకాన్ని ఎంచుకుంటాము మరియు arr [i] 0 కి సమానంగా ఉందో లేదో తనిఖీ చేయండి, అది సమానంగా ఉన్నట్లు తేలితే, మేము జోడిస్తాము -1 మొత్తానికి మరియు మొత్తానికి నిల్వ చేయడానికి, లేకపోతే మనకు 0 అని తేలకపోతే, మేము పాజిటివ్ 1 ని మొత్తానికి జోడించి మొత్తానికి నిల్వ చేస్తాము.

ఆ ప్రతికూల 1 మరియు పాజిటివ్ 1 వెనుక ఉన్న కారణం ఏమిటంటే, మేము అన్ని 0 లను -1 కు నటిస్తున్నాము మరియు వాటిని 1 తో చేర్చుతాము, కాబట్టి మనం ఎల్లప్పుడూ 0 ని పొందుతాము. కానీ మనం పాజిటివ్ 1 మొత్తాన్ని తనిఖీ చేస్తాము, ఇది మనకు ఒక అదనపు 1 ఉంటుందని సూచిస్తుంది, అప్పుడు 0 యొక్క లెక్కింపు.

మనం 1 గా -0 గా నటిస్తుంటే 1, 0, 1 తీసుకుంటాం అనుకుందాం, ఆ 0 ను మొదటి 2 సంఖ్యలతో పొందుతాము, మరియు మూడవ సంఖ్యతో, మన పరిస్థితి నెరవేరినట్లు కనుగొనవచ్చు. 1 మరియు 0 ల యొక్క ఉప-శ్రేణిని 1 కంటే 0 అదనపు గణనతో పొందాము. మా పరిస్థితి సంతృప్తికరంగా ఉంటుంది. అందువల్ల అల్గోరిథం యొక్క తరువాతి దశలో మొత్తం 1 కి సమానం మరియు అవుట్పుట్ పొడవు యొక్క పొడవును నవీకరిస్తుందా అని మేము వెతుకుతాము. చివరిగా, స్టేట్మెంట్ ఉంటే, మనకు కొత్త అవుట్పుట్ పొడవు లభిస్తే, మునుపటి అవుట్పుట్ ని ప్రస్తుత అవుట్పుట్ పొడవుతో అప్డేట్ చేయాలి మరియు మేము అవుట్పుట్ పొడవును తిరిగి ఇస్తాము.

అమలు

పొడవైన సబారే కోసం సి ++ ప్రోగ్రామ్ 1 సె లెక్కింపు 0 సెకన్ల కన్నా ఎక్కువ

#include <iostream>
#include<unordered_map>

using namespace std;

int getLongestLen(int arr[], int n)
{
    unordered_map<int, int> MAP;
    int sum = 0, outputLength= 0;

    for (int i = 0; i < n; i++)
    {

        if(arr[i] == 0)
            sum += -1;
        else
            sum += 1;


        if (sum == 1)
        {
            outputLength = i + 1;
        }
        else if (MAP.find(sum) == MAP.end())
        {
            MAP[sum] = i;
        }

        if (MAP.find(sum - 1) != MAP.end())
        {
            if (outputLength < (i - MAP[sum - 1]))
                outputLength = i - MAP[sum - 1];
        }
    }
    return outputLength;
}
int main()
{
    int arr[] = {1,0,1,1,0,0,0};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Length of the longest Sub-Array : "<<getLongestLen(arr, n);
    return 0;
}
Length of the longest Sub-Array : 5

పొడవైన సుబారే కోసం జావా ప్రోగ్రామ్ 1 సె లెక్కింపు 0 సెకన్ల కన్నా ఎక్కువ

import java.util.HashMap;

class longestSubArray01
{
    public static int getLongestLen(int arr[], int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<Integer,Integer>();
        int sum = 0, outputLength = 0;

        for (int i = 0; i < n; i++)
        {
            if(arr[i] == 0)
                sum += -1;
            else
                sum += 1;

            if (sum == 1)
                outputLength = i + 1;
            else if (!MAP.containsKey(sum))
                MAP. put(sum, i);


            if (MAP.containsKey(sum - 1))
            {
                if (outputLength < (i - MAP.get(sum - 1)))
                    outputLength = i - MAP.get(sum - 1);
            }
        }
        return outputLength;
    }
    public static void main(String[] args)
    {
        int arr[] = {1,0,1,1,0,0,0};
        int n = arr.length;
        System.out.println("Length of the longest Sub-Array : " +getLongestLen(arr, n));
    }
}
Length of the longest Sub-Array : 5

పొడవైన సబారే కోసం సంక్లిష్టత విశ్లేషణ 1 సె లెక్కింపు 0 సెకన్ల కన్నా ఎక్కువ

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

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

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

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