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

## 例

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

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

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

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

## 算法

```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.```

## 查找兩個二進制數組中具有相同總和的最長跨度的代碼

### 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）。 因此，兩個二進制數組中具有相同總和的最長跨度的整個算法具有線性時間複雜度。