# 兩個二進制數組中具有相同總和的最長跨度 > 原文： [https://www.geeksforgeeks.org/longest-span-sum-two-binary-arrays/](https://www.geeksforgeeks.org/longest-span-sum-two-binary-arrays/) 給定兩個具有相同大小 n 的二進制數組 arr1 []和 arr2 []。 求出最長公共跨度（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: 0 Input: arr1[] = {0, 0, 1, 0}; arr2[] = {1, 1, 1, 1}; Output: 1 ``` [](https://practice.geeksforgeeks.org/problem-page.php?pid=188) ## 強烈建議您在繼續解決方案之前，單擊此處進行練習。 **方法 1（簡單解決方案）** 通過考慮兩個數組的相同子數組來一一對應。 對于所有子數組，計算總和，如果總和相同且當前長度大于最大長度，則更新最大長度。 下面是 C++ 實現的簡單方法。 ## C++ ```cpp // 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[0]); ????cout << "Length of the longest common span with same " ????????????"sum is "<< longestCommonSum(arr1, arr2, n); ????return 0; } ```