兩個二進制數組中具有相同總和的最長跨度


難度級別
經常問 埃森哲 思科 確實 庫利扎 SAP實驗室 Yandex的
排列 哈希 哈希

問題陳述

系統會為您提供兩個數組,每個數組都包含二進制數。 問題陳述要求在兩個二進制數組中找到具有相同總和的最長跨度,即以(j,j)大於或等於i和arr1 [的方式從(i,j)中找出最大長度的公共子數組。 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(N) 哪裡 “ n” 是數組中元素的數量。 在這裡,由於我們使用了無序映射,所以我們遍歷了一次數組。 插入,刪除和搜索操作的時間複雜度為O(1)。 因此,兩個二進制數組中具有相同總和的最長跨度的整個算法具有線性時間複雜度。

空間複雜度

由於我們使用了unordered_map或hash映射,因此我們也具有線性空間複雜度。 O(N) 哪裡 “ n” 是數組中元素的數量。