იპოვნეთ მოცემული მასივის ყველა უნიკალური ქვე-მასივის ჯამი


Რთული ტური Easy
ხშირად ეკითხებიან Amazon Facebook რუხი ნარინჯისფერი Intuit microsoft ნაგარო
Array Hash დახარისხება

დავუშვათ, რომ მთელი რიგი გაქვთ. პრობლემა ”იპოვნეთ მოცემული მასივის ყველა უნიკალური ქვე-მასივის ჯამი” ითხოვს ყველა უნიკალური ქვე-მასივის ჯამის გასარკვევად (ქვე-მასივის ჯამი არის თითოეული ქვე-მასივის ელემენტების ჯამი).

ქვე-მასივის უნიკალური ჯამით ვგულისხმობდით იმის თქმას, რომ არც ერთ ქვე-მასივს არ აქვს იგივე მნიშვნელობა.

მაგალითი

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

იპოვნეთ მოცემული მასივის ყველა უნიკალური ქვე-მასივის ჯამი

ალგორითმი

  1. გამოაცხადეთ ა რუკა.
  2. უცნობია გამომავალი to 0.
  3. მასივის გადაკვეთა i = 0 – დან i– მდე
    1. დააყენე თანხა to 0.
    2. მასივის გადაკვეთა j = i, j- დან
      • დაამატე arr [j] მნიშვნელობა ჯამში ჯამში.
      • დაამატეთ ჯამი და მისი შემთხვევა რუკაში.
  4. გაიარეთ რუკაზე და შეამოწმეთ იმ გასაღების ჩანაწერები, რომელთა მნიშვნელობაა 1.
    1. გამომავალს დაამატეთ გასაღებების მნიშვნელობა, როდესაც ჩვენ ვხვდებით, რომ მდგომარეობა დაკმაყოფილებულია.
  5. დაბრუნების შედეგი.

განმარტება

ჩვენ გვაძლევენ მთელი რიცხვი მასივი. ჩვენი ამოცანაა გავერკვეთ ყველა უნიკალური ქვე-მასივის ჯამში. თითოეული ქვე-მასივის ჯამი იქნება თითოეული ქვე-მასივის ელემენტის ჯამი. ჩვენ ვაპირებთ გამოვიყენოთ ჰასინგი ამ კითხვის გადასაჭრელად. ჩვენ ავიღებთ მასივის თითოეულ ელემენტს, ვიწყებთ ჯამის 0-ს, ყოველთვის, როდესაც i- ს მნიშვნელობას შევცვლით. როდესაც ჩვენ შიდა მარყუჟში შევალთ, ჩვენ გადავხედავთ მასივს i to 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

ჯავის კოდი მოცემული მასივისთვის ყველა უნიკალური ქვე-მასივის ჯამის მოსაძებნად

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

სირთულის ანალიზი

დროის სირთულე

ო (ნ2სადაც "ნ" არის მასივის ელემენტების რაოდენობა. რადგან ჩვენ გამოვიყენეთ 2 ჩასმული მარყუჟი და ჯამის ძებნა ხდება O (1) - ში HashMap– ის გამოყენებით.

სივრცის სირთულე

O (n ^ 2) სადაც "ნ" არის მასივის ელემენტების რაოდენობა. რადგან უარეს შემთხვევაში შეიძლება გვქონდეს n ^ 2 განსხვავებული ქვე-მასივის ჯამი.