Најдолг распон со иста сума во две бинарни низи


Ниво на тешкотија Медиум
Често прашувано во Accenture Cisco Навистина Кулиза SAP лаборатории Yandex
Низа Хаш Хашинг

Изјава за проблем

Дадени ви се две низи од кои секоја содржи бинарен број. Изјавата за проблемот бара да се најде најдолгиот распон со иста сума во две бинарни низи, тоа е да се открие максималната должина на заедничката под-низа од (i, j) на таков начин што j е поголем или еднаков на i и arr1 [ i] + arr1 [i + 1] + arr1 [i + 2] +. + arr1 [j] = arr2 [i] + arr2 [i + 1] + arr2 [i + 2] +…. + arr2 [j].

пример

arr1[] = {1,0,1,0,0,0,1,1}

arr2[] = {1,0,1,0,1,1,0,1}
4

Објаснување: Должината на највисокиот опсег на опсегот е 4 бидејќи кај индексот 0 до 3 има збир од обете под-низи е еднаков.

Најдолг распон со иста сума во две бинарни низи

arr1[] = {1, 0, 1, 0, 1, 0}

arr2[] = {0, 1, 1, 0, 0, 0}
4

Објаснување: Должината на највисокиот опсег на опсегот е 4 затоа што кај индексот 0 до 3 има збир од обете под-низи се еднакви.

 

Алгоритам

1. Declare an array of size n.
2. Find the difference of each element’s index of both of the arrays such that arr[i]=arr1[i]-arr2[i].
3. Declare the HashMap.
4. Set sum to 0 and maxLength to 0.
5. From i=0 to i<n.
    1. Add up the value of arr[i] and sum into the sum.
    2. Check if sum ==0, then update the maxLength=i+1.
    3. Check if the map contains the sum, then update the maxLength to the maximum between maxLength and i-key’s value.
    4. Else put the sum and its index into the map.
6. Return maxLength.

Објаснување

Дадовме две бинарни низи, од кои секоја содржи бинарен број во форма на 0 и 1. Треба да го најдеме најдолгиот заеднички распон од [i, j] таков што збирот на обете низи, во тој специфичен распон , е еднаква и најдолгата е должината на тој заеднички распон. За ова, ние одиме кај нас Хашинг и дополнителна низа во која ќе ја зачуваме разликата на разликата на секој елемент на индексот на i-тата позиција на креираната низа.

Создаваме мапа, со тоа што ќе ја зачуваме вредноста на новосоздадената низа како клуч во мапата и нејзиниот индекс како вредност. Toе го откриеме максимумот на тој индекс и ќе го споредиме со maxLength што го создадовме за да ја најдеме и зачуваме максималната вредност како најдолга должина. Но, пред тоа, го земаме arr [i] и го додаваме со arr [i] и сума го чуваме во збирот. Checkе провериме дали збирот е еднаков на 0, ажурирајте ја максималната должина на i + 1. Ова е да се справи со вредностите на последниот индекс-елемент.

Проверете дали мапата содржи збир, ажурирајте ја максималната должина со тоа што ќе ја дознаете максимумот помеѓу maxLength и индексот - мапа[збир]. Друго ставете ги збирот и индексот во картата. Низата што ја направивме и иницијализиравме како разлика помеѓу обете низи игра клучна улога. По ова, ја имаме вредноста во maxLength и ја враќаме maxLength.

 

Код за да го пронајдете најдолгиот распон со иста сума во две бинарни низи

C ++ код

#include<iostream>
#include<unordered_map>

using namespace std;

int longestCommonSum(int arr1[], int arr2[], int n)
{
    int arr[n];
    for (int i=0; i<n; i++)
        arr[i] = arr1[i] - arr2[i];

    unordered_map<int, int> hM;

    int sum = 0;

    int max_len = 0;
    for (int i = 0; i < n; i++)
    {
        sum += arr[i];

        if (sum == 0)
            max_len = i + 1;

        if (hM.find(sum) != hM.end())
            max_len = max(max_len, i - hM[sum]);

        else
            hM[sum] = i;
    }
    return max_len;
}

int main()
{
    int arr1[] = {0, 1, 0, 1, 1, 1, 1};
    int arr2[] = {1, 1, 1, 1, 1, 0, 1};
    int n = sizeof(arr1)/sizeof(arr1[0]);
    cout << longestCommonSum(arr1, arr2, n);
    return 0;
}
6

 

Java код

import java.util.HashMap;

class LargestSubArr01
{
    public static int longestCommonSum(int[] arr1, int[] arr2, int n)
    {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = arr1[i] - arr2[i];

        HashMap<Integer, Integer> hM = new HashMap<>();

        int sum = 0;
        int max_len = 0;

        for (int i = 0; i < n; i++)
        {
            sum += arr[i];

            if (sum == 0)
                max_len = i + 1;

            if (hM.containsKey(sum))
                max_len = Math.max(max_len, i - hM.get(sum));

            else
                hM.put(sum, i);
        }
        return max_len;
    }
    public static void main(String args[])
    {
        int[] arr1 = {0, 1, 0, 1, 1, 1, 1};
        int[] arr2 = {1, 1, 1, 1, 1, 0, 1};
        int n = arr1.length;
        System.out.println(longestCommonSum(arr1, arr2, n));
    }
}
6

 

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

Временска комплексност

Тој) каде „Н“ е бројот на елементи во низата. Еве, еднаш сме ја прелистувале низата, и бидејќи сме користеле нередена мапа. Вметнување, бришење и пребарување операции имаат O (1) сложеност во времето. Така, целиот алгоритам за најдолг распон со иста сума во две бинарни низи има линеарна временска сложеност.

Комплексноста на просторот

Бидејќи ја користевме нередовната_мапа или хаш-мапата, имаме и линеарна вселенска комплексност. Тој) каде „Н“ е бројот на елементи во низата.