מצא סכום של כל סכום תת המערך הייחודי עבור מערך נתון


רמת קושי קַל
נשאל לעתים קרובות אמזון בעברית פייסבוק גריי אורנג ' אינטואיט מיקרוסופט נגארו
מערך בליל מִיוּן

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

לפי סכום תת מערך ייחודי, התכוונו לומר שלאף מערך משנה אין אותו ערך.

דוגמה

arr[] = {3, 1, 4, 5}
44
arr[] = {2,1,3,6}
36

מצא סכום של כל סכום תת המערך הייחודי עבור מערך נתון

אַלגוֹרִיתְם

  1. הכריז א מַפָּה.
  2. לקבוע תפוקה ל 0.
  3. חצו את המערך מ- i = 0, ל- i
    1. הגדר את סכום אל 0.
    2. חצו את המערך מ- j = i, ל- j
      • הוסף את הערך של arr [j] לסכום לסכום.
      • הוסף את הסכום והתרחשותו למפה.
  4. חצו את המפה ובדקו אם קיימים ערכי מפתח אלו שערכם הוא 1.
    1. הוסף את ערך המקשים לפלט בכל פעם שאנחנו מוצאים את התנאי מרוצה.
  5. תפוקת החזר.

הסבר

נותנים לנו מספר שלם מערך. המשימה שלנו היא לגלות את סכום כל מערכי המשנה הייחודיים. הסכום של כל תת-מערך יהיה סכום האלמנט של כל תת-מערך. אנחנו הולכים להשתמש has has כדי לפתור את השאלה הזו. אנו נאסוף כל אלמנט במערך ונאתחל את הסכום ל- 0 בכל פעם שנשנה את הערך של i. כשאנחנו נכנסים ללולאה הפנימית, נחצה מערך ממנו i ל n, והוספת כל ערך של מערך וסכום. ואז אנו מאחסנים בו זמנית את הסכום ואת הופעתו במפה. לאחר ביקור במערך כולו, גלה את כל סכום מערכי המשנה האפשריים. לאחר מכן, אנו מחפשים את הסכומים הללו במפה שההתרחשות שלהם היא פעם אחת בלבד. מכיוון שאנחנו רוצים סכום מערכי המשנה הייחודיים, אמצעים שיש להם סכומים מובחנים. לכן כשנמצא את הסכום במפה המתרחש פעם אחת, שנועד לומר שהתדירות שלו היא 1, נוסיף ונעדכן את הערך של אותם סכומים לפלט.

בהתחשב בדוגמה לכך:

דוגמה

arr [] = {3, 1, 4, 5}

ראשית, יש לנו i = 0, ואז יש לנו 3 כאלמנט ונתחיל מ -3, נוסיף 3 לסכום ונעדכן 3 במפה, ואז נוסיף 1 לסכום ונעדכן 4 במפה ואז לוקח 4 כאלמנט לסכום והוספת 7 למפה. באופן זה, נסיים את המעבר הראשון לאחר ביקור ב -5 ונעדכן 12 במפה.

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

קופונים

קוד C ++ למציאת סכום של כל סכום תת המערך הייחודי למערך נתון

#include<iostream>
#include<unordered_map>

using namespace std;

int findSumOfUnique(int arr[], int n)
{
    int output = 0;
    unordered_map<int, int> MAP;

    for (int i = 0; i < n; i++)
    {
        int sum = 0;
        for (int j = i; j < n; j++)
        {
            sum += arr[j];
            MAP[sum]++;
        }
    }
    for (auto entry : MAP)
        if (entry.second == 1)
            output += entry.first;

    return output;
}
int main()
{
    int arr[] = { 3, 1, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << findSumOfUnique(arr, n);
    return 0;
}
44

קוד Java כדי למצוא סכום של כל סכום תת-מערך הייחודי עבור מערך נתון

import java.util.HashMap;
import java.util.Map;

class SumUniqueSubArray
{
    public static int findSumOfUnique(int []arr, int n)
    {
        int output = 0;

        HashMap<Integer,Integer> MAP = new HashMap<Integer,Integer>();
        for (int i = 0; i < n; i++)
        {
            int sum = 0;
            for (int j = i; j < n; j++)
            {
                sum += arr[j];
                if (MAP.containsKey(sum))
                {
                    MAP.put(sum, MAP.get(sum) + 1);
                }
                else
                {
                    MAP.put(sum, 1);
                }
            }
        }
        for (Map.Entry<Integer,Integer> entry : MAP.entrySet())
            if (entry.getValue() == 1)
                output += entry.getKey();

        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = {3, 1, 4, 5};
        int n = arr.length;
        System.out.println(findSumOfUnique(arr, n));
    }
}
44

ניתוח מורכבות

מורכבות זמן

O (n2איפה "N" הוא מספר האלמנטים במערך. מכיוון שהשתמשנו בשתי לולאות מקוננות וחיפוש הסכום נעשה ב- O (2) באמצעות HashMap.

מורכבות בחלל

O (n ^ 2) איפה "N" הוא מספר האלמנטים של המערך. מכיוון שבמקרה הגרוע ביותר יתכן שיש לנו n ^ 2 סכום תת מערך שונה.