געפֿינען סובאַרראַי מיט אַ געגעבן סכום (האַנדלעס נעגאַטיוו נומערן)  


שוועריקייט לעוועל מיטל
אָפט געבעטן אין אַמאַזאָן קופּאָן דוניאַ דעליווערי גע העאַלטהקאַרע InfoEdge מאָנפראָג לאַבס
מענגע האַש סליידינג ווינדאָו

די פּראָבלעם "געפֿינען סובאַרראַי מיט געגעבן סאַכאַקל (האַנדלעס נעגאַטיוו נומבערס)" שטאַטן אַז איר באַקומען אַ ינטעגער מענגע, כּולל נעגאַטיוו ינטאַדזשערז און אַ נומער גערופֿן "סומע". די פּראָבלעם ויסזאָגונג פרעגט צו דרוקן די סאַב-מענגע, וואָס סאַמז אַרויף צו אַ געגעבן נומער גערופֿן "סאַכאַקל". אויב מער ווי איין סאַב-מענגע איז פאָרשטעלן ווי אונדזער פּראָדוקציע, דרוקן קיין איינער פון זיי.

בייַשפּיל  

געפֿינען סובאַרראַי מיט אַ געגעבן סכום (האַנדלעס נעגאַטיוו נומערן)שפּילקע

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 צו קסנומקס.
  3. אַריבער די מענגע, בשעת איך <n,
    1. סאַמז די ווערט פון קראַנט סומע און מענגע עלעמענט און סטאָרד עס צו קראַנט סומע.
    2. קאָנטראָלירן אויב קראַנט סומע איז גלייַך צו די סומע.
      • אויב אמת, דרוק דעם אינדעקס ווי 0 צו איך און ברעכן.
    3. קאָנטראָלירן צי די מאַפּע כּולל די ווערט קראַנט סומע.
      • אויב אמת, דרוקן די ינדעקסיז ווי די קראַנט סומע פון ​​די מאַפּע צו i און ברעכן.
    4. אויב איינער פון די געגעבן צושטאַנד טוט נישט באַפרידיקן, מיטל מיר געפֿונען גאָרנישט מיט די געגעבן סאַכאַקל.

דערקלערונג

מיר געבן אַ פּראָבלעם ויסזאָגונג צו פרעגן די סאַב-מענגע וואָס סאַמז אַרויף צו די געגעבן סאַכאַקל, און אויב עס איז געפונען מער ווי איין סאַב-מענגע, דרוקן קיין איינער פון זיי. מיר וועלן נוצן האַשמאַפּ און מיר וועלן קראָם די ווערט פון די currentSum און זיין אינדעקס אויב קיין פון די באדינגונגען זענען צופֿרידן נאָך אַדינג יעדער עלעמענט פון מענגע און currentSum (וואָס איז געווען ינישיייטיד ווי אַ 0 פריער).

זע אויך
גרעסטן סובאַררייַ מיט די זעלבע נומער פון 0 ס און 1 ס

לאָמיר באַטראַכטן אַ ביישפּיל:

בייַשפּיל

אַרר [] = {14, 1, -10, 20, 1}, סומע = 5

מיר האָבן געגעבן אַ ינטאַדזשער מענגע וואָס אויך כּולל עטלעכע נעגאַטיוו ינטאַדזשערז און אַ נומער סומע. מיר האָבן צו געפֿינען די סאַב-מענגע וואָס סומע צו די געגעבן נומער, סומע. בשעת דורכפאָר די גאנצע מענגע, מיר זאָל האַלטן אונדזער קראַנט סומע, דאָס איז וואָס גיט אונדז די מעגלעך סאַב-מענגע.

איך = 0, קראַנט סומע = 0

currentSum = currentSum + arr [i] => currentSum = 14, איצט מיר האָבן 14 אין אונדזער CurrentSum, מיר וועלן קאָנטראָלירן אויב עס איז גלייַך צו די געגעבן סומע וואָס איז 5, און דאָס איז פאַלש, מיר וועלן קאָנטראָלירן אויב מאַפּע כּולל די currentSum-sum וואָס מיטל 14-5 = 9 איז אויך פאַלש. אַזוי מיר וועלן גיין דורך די ווייַטער עלעמענט. אַזוי מיר לייגן דעם CurrentSum און איך אין די מאַפּע.

איך = 1, קראַנט סומע = 14

currentSum = currentSum + arr [i] => 14 + 1 = 15, currentSum = 15, איצט מיר האָבן 15 אין אונדזער CurrentSum, מיר וועלן קאָנטראָלירן אויב עס איז גלייַך צו די געגעבן סומע אָבער עס איז נישט צופֿרידן, מיר וועלן גיין אויב מאַפּע כּולל קראַנט סומע וואָס איז 15-5-10 איז אויך פאַלש. אַזוי מיר לייגן דעם CurrentSum און איך אין די מאַפּע.

איך = 2, קראַנט סומע = 15,

currentSum = currentSum + arr [i] => 15 + (-10), currentSum = 5, איצט מיר האָבן 15 אין אונדזער CurrentSum, מיר וועלן קאָנטראָלירן אויב עס איז גלייַך צו די געגעבן סומע וואָס איז 5, און מיר געפֿונען אַז די צושטאַנד איז צופֿרידן, מיטל מיר האָבן אונדזער פּראָדוקציע, און מיר וועלן דרוקן די ינדעקסיז פון סובאַררייַ 0 צו איך.

קאָדעקס  

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

דזשאַוואַ קאָד צו געפֿינען סובאַרראַי מיט אַ סומע (האַנדלעס נעגאַטיוו נומערן)

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

קאַמפּלעקסיטי אַנאַליסיס  

צייט קאַמפּלעקסיטי

אָ (N) ווו "N" איז די נומער פון עלעמענטן אין דער מענגע.

זע אויך
ינסערשאַן סאָרט

ספעיס קאַמפּלעקסיטי

אָ (N) ווו "N" איז די נומער פון עלעמענטן אין דער מענגע.