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

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

本文概述

给定两个二进制数组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: 0

Input: 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()
{
     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 ;
       
            // 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)

方法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()
{
     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 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

时间复杂度：Θ(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()
{
     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

输出如下：

6

本文作者：苏米特·古普塔。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: