Намерете Сума от всички уникални суми на подмасив за даден масив


Ниво на трудност Лесно
Често задавани в Амазонка Facebook GreyOrange Intuit Microsoft Нагаро
Array Хашиш сортиране

Да предположим, че имате масив от цели числа. Проблемът „Намиране на сумата на всички уникални суми подмасиви за даден масив“ иска да се намери сумата на всички уникални подмасиви (Сумата на подмасива е сумата на елементите на всеки подмасив).

Чрез уникална сума от под-масив искахме да кажем, че нито един под-масив няма същата стойност.

Пример

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. Връщане на изхода.

Обяснение

Дадено ни е цяло число масив. Нашата задача е да открием сумата на всички уникални подмасиви. Сумата от всеки под-масив ще бъде сумата от елемента на всеки под-масив. Ще използваме хеширане за решаване на този въпрос. Ще вземем всеки елемент от масив, инициализирайки сумата на 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

Анализ на сложността

Сложност във времето

На2където "н" е броят на елементите в масива. Тъй като сме използвали 2 вложени цикъла и търсенето на сума се извършва в O (1) с помощта на HashMap.

Сложност на пространството

O (n ^ 2) където "н" е броят на елементите на масива. Тъй като в най-лошия случай може да имаме n ^ 2 различни суми под-масив.