מצא מערך משנה עם סכום נתון (מטפל במספרים שליליים)


רמת קושי בינוני
נשאל לעתים קרובות אמזון בעברית קופון דוניה מסירה GE Healthcare 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 אל 0.
  3. חצה את המערך, בזמן שאני <n,
    1. מסכם את הערך של currentSum ורכיב המערך ושומר אותו ל- currentSum.
    2. בדוק אם currentSum שווה לסכום.
      • אם נכון, הדפס את האינדקס כ- 0 עד i ושבר.
    3. בדוק אם המפה מכילה את הערך currentSum-sum.
      • אם נכון, הדפס את האינדקסים כערך הסיכום הנוכחי של המפה ל- i ושבר.
    4. אם אחד מהתנאים הנתונים אינו מספק, פירושו שלא מצאנו דבר בסכום הנתון.

הסבר

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

הבה נבחן דוגמה:

דוגמה

arr [] = {14, 1, -10, 20, 1}, סכום = 5

נתנו מערך שלם המכיל גם מספרים שלמים שליליים וגם סכום מספר. עלינו לגלות את מערך המשנה המצטבר למספר הנתון, סכום. בזמן חציית המערך כולו עלינו לשמור על ה- Sum הנוכחי שלנו, זה נותן לנו את מערך המשנה האפשרי.

i = 0, currentSum = 0

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

i = 1, currentSum = 14

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

i = 2, currentSum = 15,

currentSum = currentSum + arr [i] => 15 + (-10), currentSum = 5, עכשיו יש לנו 15 בסכום הנוכחי שלנו, נבדוק אם הוא שווה לסכום הנתון שהוא 5, וגילינו שהתנאי מרוצה, פירושו שקיבלנו את התפוקה שלנו, ואז נדפיס את האינדקסים של מערך המשנה 0 עד 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

קוד Java כדי למצוא מערך משנה עם סכום נתון (מטפל במספרים שליליים)

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" הוא מספר האלמנטים במערך.