# 如何求两个二进制数组中具有相同总和的最长跨度？

2021年3月18日16:30:50 发表评论 376 次浏览

## 本文概述

``````Input: arr1[] = {0, 1, 0, 0, 0, 0};
arr2[] = {1, 0, 1, 0, 0, 1};
Output: 4
The longest span with same sum is from index 1 to 4.

Input: arr1[] = {0, 1, 0, 1, 1, 1, 1};
arr2[] = {1, 1, 1, 1, 1, 0, 1};
Output: 6
The longest span with same sum is from index 1 to 6.

Input: arr1[] = {0, 0, 0};
arr2[] = {1, 1, 1};
Output: 0

Input: arr1[] = {0, 0, 1, 0};
arr2[] = {1, 1, 1, 1};
Output: 1``````

## C ++

``````// A Simple C++ program to find longest common
// subarray of two binary arrays with same sum
#include<bits/stdc++.h>
using namespace std;

// Returns length of the longest common subarray
// with same sum
int longestCommonSum( bool arr1[], bool arr2[], int n)
{
// Initialize result
int maxLen = 0;

// One by one pick all possible starting points
// of subarrays
for ( int i=0; i<n; i++)
{
// Initialize sums of current subarrays
int sum1 = 0, sum2 = 0;

// Conider all points for starting with arr[i]
for ( int j=i; j<n; j++)
{
// Update sums
sum1 += arr1[j];
sum2 += arr2[j];

// If sums are same and current length is
// more than maxLen, update maxLen
if (sum1 == sum2)
{
int len = j-i+1;
if (len > maxLen)
maxLen = len;
}
}
}
return maxLen;
}

// Driver program to test above function
int main()
{
bool  arr1[] = {0, 1, 0, 1, 1, 1, 1};
bool  arr2[] = {1, 1, 1, 1, 1, 0, 1};
int n = sizeof (arr1)/ sizeof (arr1);
cout << "Length of the longest common span with same "
"sum is " << longestCommonSum(arr1, arr2, n);
return 0;
}``````

## Java

``````// A Simple Java program to find longest common
// subarray of two binary arrays with same sum

class Test
{
static int arr1[] = new int []{ 0 , 1 , 0 , 1 , 1 , 1 , 1 };
static int arr2[] = new int []{ 1 , 1 , 1 , 1 , 1 , 0 , 1 };

// Returns length of the longest common sum in arr1[]
// and arr2[]. Both are of same size n.
static int longestCommonSum( int n)
{
// Initialize result
int maxLen = 0 ;

// One by one pick all possible starting points
// of subarrays
for ( int i= 0 ; i<n; i++)
{
// Initialize sums of current subarrays
int sum1 = 0 , sum2 = 0 ;

// Conider all points for starting with arr[i]
for ( int j=i; j<n; j++)
{
// Update sums
sum1 += arr1[j];
sum2 += arr2[j];

// If sums are same and current length is
// more than maxLen, update maxLen
if (sum1 == sum2)
{
int len = j-i+ 1 ;
if (len > maxLen)
maxLen = len;
}
}
}
return maxLen;
}

// Driver method to test the above function
public static void main(String[] args)
{
System.out.print( "Length of the longest common span with same sum is " );
System.out.println(longestCommonSum(arr1.length));
}
}``````

## Python3

``````# A Simple python program to find longest common
# subarray of two binary arrays with same sum

# Returns length of the longest common subarray
# with same sum
def longestCommonSum(arr1, arr2, n):

# Initialize result
maxLen = 0

# One by one pick all possible starting points
# of subarrays
for i in range ( 0 , n):

# Initialize sums of current subarrays
sum1 = 0
sum2 = 0

# Conider all points for starting with arr[i]
for j in range (i, n):

# Update sums
sum1 + = arr1[j]
sum2 + = arr2[j]

# If sums are same and current length is
# more than maxLen, update maxLen
if (sum1 = = sum2):
len = j - i + 1
if ( len > maxLen):
maxLen = len

return maxLen

# Driver program to test above function
arr1 = [ 0 , 1 , 0 , 1 , 1 , 1 , 1 ]
arr2 = [ 1 , 1 , 1 , 1 , 1 , 0 , 1 ]
n = len (arr1)
print ( "Length of the longest common span with same "
"sum is" , longestCommonSum(arr1, arr2, n))

# This code is contributed by
# Smitha Dinesh Semwal``````

## C#

``````// A Simple C# program to find
// longest common subarray of
// two binary arrays with same sum
using System;

class GFG
{
static int [] arr1 = new int []{0, 1, 0, 1, 1, 1, 1};
static int [] arr2 = new int []{1, 1, 1, 1, 1, 0, 1};

// Returns length of the longest
// common sum in arr1[] and arr2[].
// Both are of same size n.
static int longestCommonSum( int n)
{
// Initialize result
int maxLen = 0;

// One by one pick all possible
// starting points of subarrays
for ( int i = 0; i < n; i++)
{
// Initialize sums of current
// subarrays
int sum1 = 0, sum2 = 0;

// Conider all points for
// starting with arr[i]
for ( int j = i; j < n; j++)
{
// Update sums
sum1 += arr1[j];
sum2 += arr2[j];

// If sums are same and current
// length is more than maxLen, // update maxLen
if (sum1 == sum2)
{
int len = j - i + 1;
if (len > maxLen)
maxLen = len;
}
}
}
return maxLen;
}

// Driver Code
public static void Main()
{
Console.Write( "Length of the longest " +
"common span with same sum is " );
Console.Write(longestCommonSum(arr1.Length));
}
}

// This code is contributed
// by ChitraNayal``````

## 的PHP

``````<?php
// A Simple PHP program to find
// longest common subarray of
// two binary arrays with same sum

// Returns length of the longest
// common subarray with same sum
function longestCommonSum( \$arr1 , \$arr2 , \$n )
{
// Initialize result
\$maxLen = 0;

// One by one pick all possible
// starting points of subarrays
for ( \$i = 0; \$i < \$n ; \$i ++)
{
// Initialize sums of
// current subarrays
\$sum1 = 0; \$sum2 = 0;

// Conider all points
// for starting with arr[i]
for ( \$j = \$i ; \$j < \$n ; \$j ++)
{
// Update sums
\$sum1 += \$arr1 [ \$j ];
\$sum2 += \$arr2 [ \$j ];

// If sums are same and current
// length is more than maxLen, // update maxLen
if ( \$sum1 == \$sum2 )
{
\$len = \$j - \$i + 1;
if ( \$len > \$maxLen )
\$maxLen = \$len ;
}
}
}
return \$maxLen ;
}

// Driver Code
\$arr1 = array (0, 1, 0, 1, 1, 1, 1);
\$arr2 = array (1, 1, 1, 1, 1, 0, 1);
\$n = sizeof( \$arr1 );
echo "Length of the longest common span " .
"with same " , "sum is " , longestCommonSum( \$arr1 , \$arr2 , \$n );

// This code is contributed by aj_36
?>``````

``Length of the longest common span with same sum is 6``

2

)

O(1)

1. 由于总共有n个元素, 因此两个数组的最大和为n。
2. 两次和之间的差从-ntoñ。因此, 总共有2n +1个可能的差值。
3. 如果两个数组的前缀和之间的差在两个点处相同, 则这两个点之间的子数组具有相同的和。

1. 创建大小为2n + 1的辅助数组, 以存储所有可能的差值的起点(请注意, 差的可能值从-n到n不等, 即, 总共有2n + 1个可能值)
2. 将所有差异的起始点初始化为-1。
3. 初始化最大长度为0, 两个数组的前缀和为0, preSum1= 0, preSum2= 0
4. 从i = 0遍历两个数组到n-1。
1. 更新前缀总和：preSum1 + = arr1 [i], preSum2 + = arr2 [i]
2. 计算当前前缀和的差：curr_diff= preSum1 – preSum2
3. 在差异数组中查找索引：diffIndex= n + curr_diff // curr_diff可以为负, 可以一直到-n
4. Ifcurr_diff为0, 那么到目前为止i + 1为maxLen
5. 否则curr_diff首次出现, 即当前diff的起始点为-1, 然后将起始点更新为i
6. 其他(curr_diff第一次没有出现), 然后将i视为终点并找到当前相同总和跨度的长度。如果此长度更大, 则更新maxLen
5. 返回maxLen

## C ++

``````// A O(n) and O(n) extra space C++ program to find
// longest common subarray of two binary arrays with
// same sum
#include<bits/stdc++.h>
using namespace std;

// Returns length of the longest common sum in arr1[]
// and arr2[]. Both are of same size n.
int longestCommonSum( bool arr1[], bool arr2[], int n)
{
// Initialize result
int maxLen = 0;

// Initialize prefix sums of two arrays
int preSum1 = 0, preSum2 = 0;

// Create an array to store staring and ending
// indexes of all possible diff values. diff[i]
// would store starting and ending points for
// difference "i-n"
int diff[2*n+1];

// Initialize all starting and ending values as -1.
memset (diff, -1, sizeof (diff));

// Traverse both arrays
for ( int i=0; i<n; i++)
{
// Update prefix sums
preSum1 += arr1[i];
preSum2 += arr2[i];

// Comput current diff and index to be used
// in diff array. Note that diff can be negative
// and can have minimum value as -1.
int curr_diff = preSum1 - preSum2;
int diffIndex = n + curr_diff;

// If current diff is 0, then there are same number
// of 1's so far in both arrays, i.e., (i+1) is
// maximum length.
if (curr_diff == 0)
maxLen = i+1;

// If current diff is seen first time, then update
// starting index of diff.
else if ( diff[diffIndex] == -1)
diff[diffIndex] = i;

// Current diff is already seen
else
{
// Find length of this same sum common span
int len = i - diff[diffIndex];

// Update max len if needed
if (len > maxLen)
maxLen = len;
}
}
return maxLen;
}

// Driver code
int main()
{
bool  arr1[] = {0, 1, 0, 1, 1, 1, 1};
bool  arr2[] = {1, 1, 1, 1, 1, 0, 1};
int n = sizeof (arr1)/ sizeof (arr1);
cout << "Length of the longest common span with same "
"sum is " << longestCommonSum(arr1, arr2, n);
return 0;
}``````

## Java

``````// A O(n) and O(n) extra space Java program to find
// longest common subarray of two binary arrays with
// same sum

class Test
{
static int arr1[] = new int []{ 0 , 1 , 0 , 1 , 1 , 1 , 1 };
static int arr2[] = new int []{ 1 , 1 , 1 , 1 , 1 , 0 , 1 };

// Returns length of the longest common sum in arr1[]
// and arr2[]. Both are of same size n.
static int longestCommonSum( int n)
{
// Initialize result
int maxLen = 0 ;

// Initialize prefix sums of two arrays
int preSum1 = 0 , preSum2 = 0 ;

// Create an array to store staring and ending
// indexes of all possible diff values. diff[i]
// would store starting and ending points for
// difference "i-n"
int diff[] = new int [ 2 *n+ 1 ];

// Initialize all starting and ending values as -1.
for ( int i = 0 ; i < diff.length; i++) {
diff[i] = - 1 ;
}

// Traverse both arrays
for ( int i= 0 ; i<n; i++)
{
// Update prefix sums
preSum1 += arr1[i];
preSum2 += arr2[i];

// Comput current diff and index to be used
// in diff array. Note that diff can be negative
// and can have minimum value as -1.
int curr_diff = preSum1 - preSum2;
int diffIndex = n + curr_diff;

// If current diff is 0, then there are same number
// of 1's so far in both arrays, i.e., (i+1) is
// maximum length.
if (curr_diff == 0 )
maxLen = i+ 1 ;

// If current diff is seen first time, then update
// starting index of diff.
else if ( diff[diffIndex] == - 1 )
diff[diffIndex] = i;

// Current diff is already seen
else
{
// Find length of this same sum common span
int len = i - diff[diffIndex];

// Update max len if needed
if (len > maxLen)
maxLen = len;
}
}
return maxLen;
}

// Driver method to test the above function
public static void main(String[] args)
{
System.out.print( "Length of the longest common span with same sum is " );
System.out.println(longestCommonSum(arr1.length));
}
}``````

## python

``````# Python program to find longest common
# subarray of two binary arrays with
# same sum

def longestCommonSum(arr1, arr2, n):

# Initialize result
maxLen = 0

# Initialize prefix sums of two arrays
presum1 = presum2 = 0

# Create a dictionary to store indices
# of all possible sums
diff = {}

# Traverse both arrays
for i in range (n):

# Update prefix sums
presum1 + = arr1[i]
presum2 + = arr2[i]

# Compute current diff which will be
# used as index in diff dictionary
curr_diff = presum1 - presum2

# If current diff is 0, then there
# are same number of 1's so far in
# both arrays, i.e., (i+1) is
# maximum length.
if curr_diff = = 0 :
maxLen = i + 1
elif curr_diff not in diff:
# save the index for this diff
diff[curr_diff] = i
else :
# calculate the span length
length = i - diff[curr_diff]
maxLen = max (maxLen, length)

return maxLen

# Driver program
arr1 = [ 0 , 1 , 0 , 1 , 1 , 1 , 1 ]
arr2 = [ 1 , 1 , 1 , 1 , 1 , 0 , 1 ]
print ( "Length of the longest common" , " span with same" , end = " " )
print ( "sum is" , longestCommonSum(arr1, arr2, len (arr1)))

# This code is contributed by Abhijeet Nautiyal``````

## C#

``````// A O(n) and O(n) extra space C# program
// to find longest common subarray of two
// binary arrays with same sum
using System;

class GFG
{
static int [] arr1 = new int []{0, 1, 0, 1, 1, 1, 1};
static int [] arr2 = new int []{1, 1, 1, 1, 1, 0, 1};

// Returns length of the longest
// common sum in arr1[] and arr2[].
// Both are of same size n.
static int longestCommonSum( int n)
{
// Initialize result
int maxLen = 0;

// Initialize prefix sums of
// two arrays
int preSum1 = 0, preSum2 = 0;

// Create an array to store staring
// and ending indexes of all possible
// diff values. diff[i] would store
// starting and ending points for
// difference "i-n"
int [] diff = new int [2 * n + 1];

// Initialize all starting and ending
// values as -1.
for ( int i = 0; i < diff.Length; i++)
{
diff[i] = -1;
}

// Traverse both arrays
for ( int i = 0; i < n; i++)
{
// Update prefix sums
preSum1 += arr1[i];
preSum2 += arr2[i];

// Compute current diff and index to
// be used in diff array. Note that
// diff can be negative and can have
// minimum value as -1.
int curr_diff = preSum1 - preSum2;
int diffIndex = n + curr_diff;

// If current diff is 0, then there
// are same number of 1's so far in
// both arrays, i.e., (i+1) is
// maximum length.
if (curr_diff == 0)
maxLen = i + 1;

// If current diff is seen first time, // then update starting index of diff.
else if ( diff[diffIndex] == -1)
diff[diffIndex] = i;

// Current diff is already seen
else
{
// Find length of this same
// sum common span
int len = i - diff[diffIndex];

// Update max len if needed
if (len > maxLen)
maxLen = len;
}
}
return maxLen;
}

// Driver Code
public static void Main()
{
Console.Write( "Length of the longest common " +
"span with same sum is " );
Console.WriteLine(longestCommonSum(arr1.Length));
}
}

// This code is contributed
// by Akanksha Rai(Abby_akku)``````

``Length of the longest common span with same sum is 6``

1. 找到差异数组arr [], 使arr [i] = arr1 [i] – arr2 [i]。
2. 最大数目等于0和1的子数组在差异数组中。

## C ++

``````// C++ program to find largest subarray
// with equal number of 0's and 1's.
#include <bits/stdc++.h>
using namespace std;

// Returns largest common subarray with equal
// number of 0s and 1s in both of t
int longestCommonSum( bool arr1[], bool arr2[], int n)
{
// Find difference between the two
int arr[n];
for ( int i=0; i<n; i++)
arr[i] = arr1[i] - arr2[i];

// Creates an empty hashMap hM
unordered_map< int , int > hM;

int sum = 0;     // Initialize sum of elements
int max_len = 0; // Initialize result

// Traverse through the given array
for ( int i = 0; i < n; i++)
{
// Add current element to sum
sum += arr[i];

// To handle sum=0 at last index
if (sum == 0)
max_len = i + 1;

// If this sum is seen before, // then update max_len if required
if (hM.find(sum) != hM.end())
max_len = max(max_len, i - hM[sum]);

else // Else put this sum in hash table
hM[sum] = i;
}

return max_len;
}

// Driver progra+m to test above function
int main()
{
bool  arr1[] = {0, 1, 0, 1, 1, 1, 1};
bool  arr2[] = {1, 1, 1, 1, 1, 0, 1};
int n = sizeof (arr1)/ sizeof (arr1);
cout << longestCommonSum(arr1, arr2, n);
return 0;
}``````

## Java

``````// Java program to find largest subarray
// with equal number of 0's and 1's.
import java.io.*;
import java.util.*;

class GFG
{

// Returns largest common subarray with equal
// number of 0s and 1s
static int longestCommonSum( int [] arr1, int [] arr2, int n)
{
// Find difference between the two
int [] arr = new int [n];
for ( int i = 0 ; i < n; i++)
arr[i] = arr1[i] - arr2[i];

// Creates an empty hashMap hM
HashMap<Integer, Integer> hM = new HashMap<>();

int sum = 0 ;     // Initialize sum of elements
int max_len = 0 ; // Initialize result

// Traverse through the given array
for ( int i = 0 ; i < n; i++)
{
// Add current element to sum
sum += arr[i];

// To handle sum=0 at last index
if (sum == 0 )
max_len = i + 1 ;

// If this sum is seen before, // then update max_len if required
if (hM.containsKey(sum))
max_len = Math.max(max_len, i - hM.get(sum));

else // Else put this sum in hash table
hM.put(sum, i);
}
return max_len;
}

// Driver code
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));
}
}

// This code is contributed by rachana soma``````

``6`` 