本文概述给定两个二进制数组arr1 []和arr2 [], 它们的大小为n。求出最长公共跨度(i, j)的长度, 其中j> = i, 使得arr1 [i] + arr1 [i + 1] +…。 + arr1 [j] = arr2 [i] + arr2 [i + 1] +…。 + arr2 [j]。
预期时间复杂度为Θ(n)。
例子 ：

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: 0Input: arr1[] = {0, 0, 1, 0}; arr2[] = {1, 1, 1, 1}; Output: 1

强烈建议你在继续解决方案之前, 单击此处进行练习。方法1(简单解决方案)
一一考虑两个阵列的相同子阵列。对于所有子数组, 请计算总和, 如果总和相同且当前长度大于最大长度, 则更新最大长度。下面是C ++实现的简单方法。
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() { boolarr1[] = {0, 1, 0, 1, 1, 1, 1}; boolarr2[] = {1, 1, 1, 1, 1, 0, 1}; int n = sizeof (arr1)/ sizeof (arr1[0]); 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 sumclass 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 = lenreturn 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)
方法2(使用辅助阵列)
该想法基于以下观察。

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() { boolarr1[] = {0, 1, 0, 1, 1, 1, 1}; boolarr2[] = {1, 1, 1, 1, 1, 0, 1}; int n = sizeof (arr1)/ sizeof (arr1[0]); 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 sumclass 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 sumdef 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

时间复杂度：Θ(n)
辅助空间：Θ(n)
方法3(使用哈希)

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() { boolarr1[] = {0, 1, 0, 1, 1, 1, 1}; boolarr2[] = {1, 1, 1, 1, 1, 0, 1}; int n = sizeof (arr1)/ sizeof (arr1[0]); 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

【如何求两个二进制数组中具有相同总和的最长跨度（）】本文作者：苏米特·古普塔。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。

推荐阅读

• 

  旧手机如何开发利用
• 

  云享越野直播卖货真实吗，云享云北京科技有限公司
• 

  钉钉直播细节，钉钉直播内容
• 

  开学季
• 

  寒假总动员
• 

  jquery|单选按钮radio样式的改变
• 

  《无主之地2》官方繁中日语语音设置方法
• 

  护肤品是不是不能放卫生间 护肤品放卫生间可以吗
• 

  离婚后可否重新争夺抚养权？ 离婚之后还可以争夺抚养权吗
• 

  龙井茶叶的8大功效 龙井茶叶的功效
• 

  6种“时尚”活法 毁掉你的健康
• 

  TypeScript入门介绍和版本 – TypeScript开发教程
• 

  心律不齐能打新冠疫苗吗
• 

  厨房有阳台门怎么装修
• 

  民间气象谚语大全 气象谚语大全
• 

  佛手瓜的皮能吃吗
• 

  中央空调定时灯一直闪是怎么回事,区别是全方位的
• 

  胃镜|胃镜下去全是食物，重新再做胃镜，但家属拒绝二次缴费，怎么办？
• 

  梦到小老鼠是什么意思周公解梦 梦到小老鼠是什么意思周公解梦
• 

  满山红 满山红诗句

• Python如何在Tkinter中创建一个按钮（）
• 算法问题（收费和蛋糕问题）
• 如何使用Jupyter Notebook（-终极指南）
• Angular CLI | Angular项目部署详细指南
• PHP imagechar()函数用法详细指南
• 如何从Hello World示例开始Java编程（）
• 64gu盘做打开盘制作详细说明
• usb pe打开盘制作详细说明
• 打开盘制作详细说明