दिइएको योगफलको साथ सबबार (फेला पार्नुहोस् नकारात्मक नम्बरहरू)  


कठिनाई तह मध्यम
बारम्बार सोधिन्छ अमेजन कुपनडुनिया दिल्लीवरी जीई हेल्थकेयर जानकारीEdge मूनफ्रग ल्याबहरू
एरे हैश स्लाइडि Wind विन्डो

समस्या "दिइएको योगको साथ सबबार्रे फेला पार्नुहोस् (नकारात्मक नम्बरहरू ह्याण्डल गर्दछ)" भन्छन् कि तपाईंलाई एक दिइन्छ पूर्णांक array, नकारात्मक पूर्णा containing्क सहित र एक संख्या "योग" पनि समावेश गर्दछ। समस्या कथनले सब-एरे प्रिन्ट गर्न सोध्दछ, जुन "संख्या" भनिएको संख्यामा योगफल दिन्छ। यदि एक भन्दा बढी उप-एर्रे हाम्रो आउटपुटको रूपमा उपस्थित छन् भने, तिनीहरूलाई कुनै पनि प्रिन्ट गर्नुहोस्।

उदाहरणका  

दिइएको योगफलको साथ सबबार (फेला पार्नुहोस् नकारात्मक नम्बरहरू)

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. यदि वर्तमानसम योगफलको बराबर हो भने जाँच गर्नुहोस्।
      • यदि सहि छ भने, तब अनुक्रमणिका ० को रूपमा i प्रिन्ट गर्नुहोस् र ब्रेक गर्नुहोस्।
    3. यदि नक्शाले मौजूदा समम-योग समावेश गर्दछ भने जाँच गर्नुहोस्।
      • यदि सहि छ भने अनुक्रमणिकालाई नक्शाको वर्तमानसूम मानको रूपमा प्रिन्ट गर्नुहोस् i र ब्रेक गर्नुहोस्।
    4. यदि दिईएको कुनै पनि शर्तले सन्तुष्ट हुँदैन भने, यसको अर्थ हामीले दिईएको रकमको साथ हामीले केही पनि पाएनौं।

स्पष्टीकरण

हामीलाई एउटा समस्या कथन दिइन्छ जुन उप एरे पत्ता लगाउन सोध्यो जुन दिइएको योगफलको योगफल र यदि त्यहाँ एक भन्दा बढी उप-एरे भेटिए भने, ती मध्ये कुनै पनि प्रिन्ट गर्नुहोस्। हामी प्रयोग गर्न जाँदैछौं हशम्याप र हामी यसको मान भण्डार गर्न जाँदैछौं करेन्टसम र यसको अनुक्रमणिका यदि कुनै पनि तत्वहरूको प्रत्येक तत्व जोडेर सन्तुष्ट भएन array र करेंटसम (जुन ० पहिले नै सुरूवात गरिएको थियो)।

पनि हेर्नुहोस्
०s र १ हरूको समान संख्याको साथ सब भन्दा ठूलो सबभ्रे

हामी एक उदाहरण विचार गरौं:

उदाहरणका

एर [] = {१,, १, -१०, २०, १}, योग = 14

हामीले एक पूर्णा ar्क एरे दिईएको छ जुन केहि नकारात्मक पूर्णा containing्क साथै संख्या संख्या समावेश गर्दछ। हामीले उप-एर्रे फेला पार्नु पर्छ जुन दिइएको संख्या, योगमा थप गर्दछ। सम्पूर्ण एर्रे ट्र्याभरिंग गर्दा हामीले हाम्रो हालको सुसमलाई कायम राख्नुपर्छ, यसले हामीलाई सम्भावित सब-एरे दिन्छ।

i = 0, करेन्टसम = ०

करेन्टसम = करंटसम + एर [i] => करेन्टसम = १,, अब हामीसँग हाम्रो करन्टसममा १ have छ, हामी जाँच गर्छौं यदि यो दिइएको योग बराबर हो कि 14 हो, र त्यो गलत हो, हामी जाँच गर्नेछौं यदि नक्सामा करेन्टसम योग जसको मतलब १-14--5 = 14 पनि गलत छ। त्यसैले हामी अर्को तत्व मार्फत जान्छौं। हामी नक्शामा हालको समम र म थप्दछौं।

i = 1, करेन्टसम = ०

करेन्टसम = करंटसम + एर [i] => १ + + १ = १,, करंटसम = १,, अब हामीसँग हाम्रो वर्तमानमा १ 14 छ, हामी जाँच गर्छौं यदि यो दिइएको राशि बराबर छ तर यो सन्तुष्ट छैन, हामी जानेछौं यदि नक्शाले वर्तमान समम योग समावेश गर्दछ जुन १-1--15-१० पनि गलत छ। हामी नक्शामा हालको समम र म थप्दछौं।

i = 2, करेंटसम = १ 15,

करेन्टसम = करंटसम + एर [i] => १ + + (-15), करेन्टसम =,, अब हामीसँग हाम्रो करन्टसममा १ 10 छ, हामी जाँच गर्छौं यदि यो दिइएको योगफल equal को बराबर छ कि छैन, र हामीले पत्ता लगायौं कन्डिसन सन्तुष्ट छ, यसको मतलब हामीले हाम्रो आउटपुट पाएका छौं, तब हामी सब्रे्रे ० देखि 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

जाभा कोड दिइएको राशि संग subarray फेला पार्न (नकारात्मक नम्बरहरू ह्यान्डलहरू)

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" एर्रेमा एलिमेन्ट्सको संख्या हो।