Най-дълъг интервал със същата сума в два двоични масива


Ниво на трудност M
Често задавани в Accenture Cisco Наистина Кулиза SAP Labs Yandex
Array Хашиш хеширане

Декларация за проблема

Получават се два масива, всеки от които съдържа двоично число. Изложението на проблема изисква да се намери най-дългият обхват със същата сума в два двоични масива, т.е. да се открие общата подмасив с максимална дължина от (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-ти индексен елемент в i-та позиция на създадения масив.

Ние създаваме карта, в която ще съхраняваме стойността на новосъздадения масив като ключ в картата и неговия индекс като стойност. Ще открием максимума на този индекс и ще го сравним с maxLength, който създадохме, за да намерим и съхраним максималната стойност като най-дългата дължина. Но преди това вземаме arr [i] и го добавяме с arr [i] и сумираме и го съхраняваме в сумата. Ще проверим дали сумата е равна на 0, актуализираме maxLength до i + 1. Това е за обработка на стойностите в последния елемент на индекса.

Проверете дали картата съдържа сумата, след това актуализирайте максималната дължина, като откриете максималната между maxLength и index - карта[сума]. В противен случай сложете сумата и индекса в картата. Масивът, който направихме и инициализирахме като разлика между двата масива, играе ключова роля. След това имаме стойността в 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). По този начин целият алгоритъм за най-дългия период с една и съща сума в два двоични масива има линейна времева сложност.

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

Тъй като използвахме unordered_map или hash map, имаме и линейна сложност на пространството. О (п) където "н" е броят на елементите в масива.