给定两个二进制数组，arr1[]和arr2[]的大小相同n。求最长公共跨度（i，j）的长度，其中j>=i，使得arr1[i]+arr1[i+1]+..+arr1[j]=arr2[i]+arr2[i+1]+arr2[j]。 预期的时间复杂度为Θ（n）。
null
例如：
Input: arr1[] = {0, 1, 0, 0, 0, 0}; arr2[] = {1, 0, 1, 0, 0, 1};Output: 4The 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: 6The 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; // Consider 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[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 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 ; // Consider 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 # Consider 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; // Consider 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; // Consider 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 ?> |
Javascript
<script> // A Simple Javascript program to find // longest common subarray of // two binary arrays with same sum let arr1 = [0, 1, 0, 1, 1, 1, 1]; let arr2 = [1, 1, 1, 1, 1, 0, 1]; // Returns length of the longest // common sum in arr1[] and arr2[]. // Both are of same size n. function longestCommonSum(n) { // Initialize result let maxLen = 0; // One by one pick all possible // starting points of subarrays for (let i = 0; i < n; i++) { // Initialize sums of current // subarrays let sum1 = 0, sum2 = 0; // Consider all points for // starting with arr[i] for (let 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) { let len = j - i + 1; if (len > maxLen) maxLen = len; } } } return maxLen; } document.write( "Length of the longest " + "common span with same sum is " ); document.write(longestCommonSum(arr1.length)); </script> |
输出：
Length of the longest common span with same sum is 6
时间复杂性： O（n） 2. ) 辅助空间： O（1）
方法2（使用辅助阵列） 这个想法基于以下观察结果。
- 因为总共有n个元素，所以两个数组的最大和都是n。
- 两个总和之间的差值各不相同 -n 到 N 所以总共有2n+1个可能的差值。
- 如果两个数组的前缀和之间的差异在两点处变得相同，则这两点之间的子数组具有相同的和。
下面是完整的算法。
- 创建一个大小为2n+1的辅助数组，以存储所有可能的差异值的起点（注意，可能的差异值从-n到n不等，即总共有2n+1个可能值）
- 将所有差异的起点初始化为-1。
- 初始化 麦克斯伦 两个数组的前缀和均为0， 假定1 = 0, 假定 = 0
- 从i=0到n-1遍历两个数组。
- 更新前缀和：preSum1+=arr1[i]，preSum2+=arr2[i]
- 计算当前前缀和的差值： 时差 =preSum1–preSum2
- 在差异数组中查找索引： 扩散指数 =n+curr_diff//curr_diff可以是负数，可以一直到-n
- 如果 curr_diff是0，那么到目前为止i+1是maxLen
- 否则如果 第一次看到curr_diff，即当前diff的起点为-1，然后将起点更新为i
- 其他的 （CurrayDIFF没有第一次看到），然后将I作为结束点，查找当前长度相同的总和跨度。如果此长度更大，则更新maxLen
- 返回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 starting 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]; // 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 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[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 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 starting 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 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 starting // 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) |
Javascript
<script> // A O(n) and O(n) extra space // Javascript program to find longest // common subarray of two binary arrays // with same sum let arr1 = [0, 1, 0, 1, 1, 1, 1]; let arr2 = [1, 1, 1, 1, 1, 0, 1]; // Returns length of the longest // common sum in arr1[] and arr2[]. // Both are of same size n. function longestCommonSum(n) { // Initialize result let maxLen = 0; // Initialize prefix sums of // two arrays let preSum1 = 0, preSum2 = 0; // Create an array to store starting // and ending indexes of all possible // diff values. diff[i] would store // starting and ending points for // difference "i-n" let diff = new Array(2 * n + 1); // Initialize all starting and ending // values as -1. for (let i = 0; i < diff.length; i++) { diff[i] = -1; } // Traverse both arrays for (let 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. let curr_diff = preSum1 - preSum2; let 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 let len = i - diff[diffIndex]; // Update max len if needed if (len > maxLen) maxLen = len; } } return maxLen; } document.write( "Length of the longest common " + "span with same sum is " ); document.write(longestCommonSum(arr1.length)); </script> |
输出：
Length of the longest common span with same sum is 6
时间复杂性 ：Θ（n） 辅助空间 ：Θ（n）
方法3（使用哈希）
- 求差分数组arr[]使arr[i]=arr1[i]-arr2[i]。
- 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 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[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 |
Python3
# Python program to find largest subarray # with equal number of 0's and 1's. # Returns largest common subarray with equal # number of 0s and 1s def longestCommonSum(arr1, arr2, n): # Find difference between the two arr = [ 0 for i in range (n)] for i in range (n): arr[i] = arr1[i] - arr2[i]; # Creates an empty hashMap hM hm = {} sum = 0 # Initialize sum of elements max_len = 0 #Initialize result # Traverse through the given array for i in range (n): # 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 sum in hm: max_len = max (max_len, i - hm[ sum ]) else : # Else put this sum in hash table hm[ sum ] = i return max_len # Driver code arr1 = [ 0 , 1 , 0 , 1 , 1 , 1 , 1 ] arr2 = [ 1 , 1 , 1 , 1 , 1 , 0 , 1 ] n = len (arr1) print (longestCommonSum(arr1, arr2, n)) # This code is contributed by rag2127 |
C#
// C# program to find largest subarray // with equal number of 0's and 1's. using System; using System.Collections.Generic; public 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 Dictionary< int , int > hM = new Dictionary< int , int >(); 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[sum]); else // Else put this sum in hash table hM[sum] = i; } return max_len; } // Driver code static public void Main () { int [] arr1 = {0, 1, 0, 1, 1, 1, 1}; int [] arr2 = {1, 1, 1, 1, 1, 0, 1}; int n = arr1.Length; Console.WriteLine(longestCommonSum(arr1, arr2, n)); } } // This code is contributed by avanitrachhadiya2155 |
Javascript
<script> // Javascript program to find largest subarray // with equal number of 0's and 1's. // Returns largest common subarray with equal // number of 0s and 1s function longestCommonSum(arr1,arr2,n) { // Find difference between the two let arr = new Array(n); for (let i = 0; i < n; i++) arr[i] = arr1[i] - arr2[i]; // Creates an empty hashMap hM let hM = new Map(); let sum = 0; // Initialize sum of elements let max_len = 0; // Initialize result // Traverse through the given array for (let 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.has(sum)) max_len = Math.max(max_len, i - hM.get(sum)); else // Else put this sum in hash table hM.set(sum, i); } return max_len; } // Driver code let arr1=[0, 1, 0, 1, 1, 1, 1]; let arr2=[1, 1, 1, 1, 1, 0, 1]; let n = arr1.length; document.write(longestCommonSum(arr1, arr2, n)); // This code is contributed by ab2127 </script> |
输出：
6
https://www.youtube.com/watch?v=xtfj4
-r_-Ahs 本文由 苏密特·古普塔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
