Самый длинный интервал с одинаковой суммой в двух двоичных массивах


Сложный уровень средний
Часто спрашивают в Accenture Cisco В самом деле Кулиза SAP Labs Яндекс
массив Hash хеширования

Постановка задачи

Вам даны два массива, каждый из которых содержит двоичное число. В постановке задачи предлагается найти самый длинный промежуток с одинаковой суммой в двух двоичных массивах, то есть найти общий подмассив максимальной длины из (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 и индексом - карта[сумма]. В противном случае поместите сумму и индекс на карту. Массив, который мы создали и инициализировали как разницу между обоими массивами, играет ключевую роль. После этого у нас есть значение 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 или хеш-карту, у нас также есть линейная пространственная сложность. О (п) в котором «Н» это количество элементов в массиве.