算法题：将一个数组拆分成两个相等的和子数组

2021年4月14日14:56:25 发表评论 1,045 次浏览

本文概述

给定一个大于零的整数数组, 请查找是否有可能将其拆分为两个子数组(无需对元素进行重新排序), 以使两个子数组的总和相同。打印两个子数组。

例子 ：

Input : Arr[] = { 1 , 2 , 3 , 4 , 5 , 5  }
Output :  { 1 2 3 4 } 
          { 5 , 5 }

Input : Arr[] = { 4, 1, 2, 3 }
Output : {4 1}
         {2 3}

Input : Arr[] = { 4, 3, 2, 1}
Output : Not Possible

一种简单的解决方案：

将运行两个循环以拆分数组, 并检查是否可以将数组拆分为两部分, 以使first_part的总和等于second_part的总和。

以下是上述想法的实现。

C++

//C++ program to split an array into Two
//equal sum subarrays
#include<bits/stdc++.h>
using namespace std;
  
//Returns split point. If not possible, then
//return -1.
int findSplitPoint( int arr[], int n)
{
     int leftSum = 0 ;
  
     //traverse array element
     for ( int i = 0; i <n; i++)
     {
         //add current element to left Sum
         leftSum += arr[i] ;
  
         //find sum of rest array elements (rightSum)
         int rightSum = 0 ;
         for ( int j = i+1 ; j <n ; j++ )
             rightSum += arr[j] ;
  
         //split point index
         if (leftSum == rightSum)
             return i+1 ;
     }
  
     //if it is not possible to split array into
     //two parts
     return -1;
}
  
//Prints two parts after finding split point using
//findSplitPoint()
void printTwoParts( int arr[], int n)
{
     int splitPoint = findSplitPoint(arr, n);
  
     if (splitPoint == -1 || splitPoint == n )
     {
         cout <<"Not Possible" <<endl;
         return ;
     }
     for ( int i = 0; i <n; i++)
     {
         if (splitPoint == i)
             cout <<endl;
         cout <<arr[i] <<" " ;
     }
}
  
//driver program
int main()
{
     int arr[] = {1 , 2 , 3 , 4 , 5 , 5 };
     int n = sizeof (arr)/sizeof (arr[0]);
     printTwoParts(arr, n);
     return 0;
}

Java

//Java program to split an array 
//into two equal sum subarrays
import java.io.*;
  
class GFG {
  
     //Returns split point. If 
     //not possible, then return -1.
     static int findSplitPoint( int arr[], int n)
     {
      
     int leftSum = 0 ;
  
     //traverse array element
     for ( int i = 0 ; i <n; i++)
     {
         //add current element to left Sum
         leftSum += arr[i] ;
  
         //find sum of rest array
         //elements (rightSum)
         int rightSum = 0 ;
          
         for ( int j = i+ 1 ; j <n ; j++ )
             rightSum += arr[j] ;
  
         //split point index
         if (leftSum == rightSum)
             return i+ 1 ;
     }
  
     //if it is not possible to 
     //split array into two parts
     return - 1 ;
     }   
  
     //Prints two parts after finding 
     //split point using findSplitPoint()
     static void printTwoParts( int arr[], int n)
     {
      
         int splitPoint = findSplitPoint(arr, n);
      
         if (splitPoint == - 1 || splitPoint == n )
         {
             System.out.println( "Not Possible" );
             return ;
         }
          
         for ( int i = 0 ; i <n; i++)
         {
             if (splitPoint == i)
                System.out.println();
                 
             System.out.print(arr[i] + " " );
              
         }
     }
  
//Driver program
      
     public static void main (String[] args) {
      
     int arr[] = { 1 , 2 , 3 , 4 , 5 , 5 };
     int n = arr.length;
     printTwoParts(arr, n);
      
     }
}
  
//This code is contributed by vt_m

Python3

# Python3 program to split an array into Two
# equal sum subarrays
   
# Returns split point. If not possible, then
# return -1.
def findSplitPoint(arr, n) :
   
     leftSum = 0 
    
     # traverse array element
     for i in range ( 0 , n) :
       
         # add current element to left Sum
         leftSum + = arr[i] 
    
         # find sum of rest array elements (rightSum)
         rightSum = 0 
         for j in range (i + 1 , n) :
             rightSum + = arr[j] 
    
         # split poindex
         if (leftSum = = rightSum) :
             return i + 1 
       
    
     # if it is not possible to split array into
     # two parts
     return - 1
   
    
# Prints two parts after finding split pousing
# findSplitPoint()
def printTwoParts(arr, n) :
   
     splitPo = findSplitPoint(arr, n)
    
     if (splitPo = = - 1 or splitPo = = n ) :
         print ( "Not Possible" )
         return
       
     for i in range ( 0 , n) :
         if (splitPo = = i) :
             print ("")
         print ( str (arr[i]) + ' ' , end = '')
   
# driver program
arr = [ 1 , 2 , 3 , 4 , 5 , 5 ]
n = len (arr)
printTwoParts(arr, n)
  
# This code is contributed by Manish Shaw
# (manishshaw1)

C#

//C# program to split an array 
//into two equal sum subarrays
using System;
  
class GFG {
  
     //Returns split point. If 
     //not possible, then return -1.
     static int findSplitPoint( int []arr, int n)
     {
      
         int leftSum = 0 ;
      
         //traverse array element
         for ( int i = 0; i <n; i++)
         {
              
             //add current element to left Sum
             leftSum += arr[i] ;
      
             //find sum of rest array
             //elements (rightSum)
             int rightSum = 0 ;
              
             for ( int j = i+1 ; j <n ; j++ )
                 rightSum += arr[j] ;
      
             //split point index
             if (leftSum == rightSum)
                 return i+1 ;
         }
  
         //if it is not possible to 
         //split array into two parts
         return -1;
     } 
  
     //Prints two parts after finding 
     //split point using findSplitPoint()
     static void printTwoParts( int []arr, int n)
     {
      
         int splitPoint = findSplitPoint(arr, n);
      
         if (splitPoint == -1 || splitPoint == n )
         {
             Console.Write( "Not Possible" );
             return ;
         }
          
         for ( int i = 0; i <n; i++)
         {
             if (splitPoint == i)
             Console.WriteLine();
                  
             Console.Write(arr[i] + " " );
         }
     }
  
     //Driver program
     public static void Main ()
     {
         int []arr = {1 , 2 , 3 , 4 , 5 , 5 };
         int n = arr.Length;
         printTwoParts(arr, n);
     }
}
  
//This code is contributed by nitin mittal

PHP

<?php
//PHP program to split
//an array into Two
//equal sum subarrays
  
//Returns split point. 
//If not possible, then
//return -1.
function findSplitPoint( $arr , $n )
{
     $leftSum = 0 ;
  
     //traverse array element
     for ( $i = 0; $i <$n ; $i ++)
     {
          
         //add current element 
         //to left Sum
         $leftSum += $arr [ $i ] ;
  
         //find sum of rest array 
         //elements (rightSum)
         $rightSum = 0 ;
         for ( $j = $i + 1 ; $j <$n ; $j ++ )
             $rightSum += $arr [ $j ] ;
  
         //split point index
         if ( $leftSum == $rightSum )
             return $i +1 ;
     }
  
     //if it is not possible 
     //to split array into
     //two parts
     return -1;
}
  
//Prints two parts after 
//finding split point using
//findSplitPoint()
function printTwoParts( $arr , $n )
{
     $splitPoint = findSplitPoint( $arr , $n );
  
     if ( $splitPoint == -1 or $splitPoint == $n )
     {
         echo "Not Possible" ;
         return ;
     }
     for ( $i = 0; $i <$n ; $i ++)
     {
         if ( $splitPoint == $i )
             echo "\n" ;
         echo $arr [ $i ] , " " ;
     }
}
  
     //Driver Code
     $arr = array (1 , 2 , 3 , 4 , 5 , 5);
     $n = count ( $arr );
     printTwoParts( $arr , $n );
      
//This code is contributed by anuj_67.
?>

输出如下：

1 2 3 4
5 5

时间复杂度：O(n

2

)

辅助空间：O(1)

An高效的解决方案首先要从左到右计算整个数组的和。现在我们从右边遍历数组, 并跟踪右边的和, 可以通过从整个和中减去当前元素来计算左边的和。

以下是上述想法的实现。

C++

//C++ program to split an array into Two
//equal sum subarrays
#include<bits/stdc++.h>
using namespace std;
  
//Returns split point. If not possible, then
//return -1.
int findSplitPoint( int arr[], int n)
{
     //traverse array element and compute sum
     //of whole array
     int leftSum = 0;
     for ( int i = 0 ; i <n ; i++)
         leftSum += arr[i];
  
     //again traverse array and compute right sum
     //and also check left_sum equal to right
     //sum or not
     int rightSum = 0;
     for ( int i=n-1; i>= 0; i--)
     {
         //add current element to right_sum
         rightSum += arr[i];
  
         //exclude current element to the left_sum
         leftSum -=  arr[i] ;
  
         if (rightSum == leftSum)
             return i ;
     }
  
     //if it is not possible to split array
     //into two parts.
     return -1;
}
  
//Prints two parts after finding split point using
//findSplitPoint()
void printTwoParts( int arr[], int n)
{
     int splitPoint = findSplitPoint(arr, n);
  
     if (splitPoint == -1 || splitPoint == n )
     {
         cout <<"Not Possible" <<endl;
         return ;
     }
     for ( int i = 0; i <n; i++)
     {
         if (splitPoint == i)
             cout <<endl;
         cout <<arr[i] <<" " ;
     }
}
  
//driver program
int main()
{
     int arr[] = {1 , 2 , 3 , 4 , 5 , 5 };
     int n = sizeof (arr)/sizeof (arr[0]);
     printTwoParts(arr, n);
     return 0;
}

Java

//java program to split an array 
//into Two equal sum subarrays
import java.io.*;
  
class GFG {
  
     //Returns split point. If not possible, then
     //return -1.
     static int findSplitPoint( int arr[], int n)
     {
      
     //traverse array element and compute sum
     //of whole array
     int leftSum = 0 ;
      
     for ( int i = 0 ; i <n ; i++)
         leftSum += arr[i];
  
     //again traverse array and compute right 
     //sum and also check left_sum equal to 
     //right sum or not
     int rightSum = 0 ;
      
     for ( int i = n- 1 ; i>= 0 ; i--)
     {
         //add current element to right_sum
         rightSum += arr[i];
  
         //exclude current element to the left_sum
         leftSum -= arr[i] ;
  
         if (rightSum == leftSum)
             return i ;
     }
  
     //if it is not possible to split array
     //into two parts.
     return - 1 ;
     }
  
     //Prints two parts after finding split 
     //point using findSplitPoint()
     static void printTwoParts( int arr[], int n)
     {
         int splitPoint = findSplitPoint(arr, n);
      
         if (splitPoint == - 1 || splitPoint == n )
         {
             System.out.println( "Not Possible" );
             return ;
         }
         for ( int i = 0 ; i <n; i++)
         {
             if (splitPoint == i)
                 System.out.println();
                  
             System.out.print(arr[i] + " " );
         }
     }
  
     //Driver program
     public static void main (String[] args) {
      
     int arr[] = { 1 , 2 , 3 , 4 , 5 , 5 };
     int n = arr.length;
      
     printTwoParts(arr, n);
          
     }
}
  
//This code is contributed by vt_m

Python3

# Python3 program to split 
# an array into Two
# equal sum subarrays
   
# Returns split point. 
# If not possible, # then return -1.
def findSplitPoint(arr, n) :
     # traverse array element and 
     # compute sum of whole array
     leftSum = 0
     for i in range ( 0 , n) :
         leftSum + = arr[i]
   
     # again traverse array and
     # compute right sum and also 
     # check left_sum equal to 
     # right sum or not
     rightSum = 0
     for i in range (n - 1 , - 1 , - 1 ) :
         # add current element
         # to right_sum
         rightSum + = arr[i]
   
         # exclude current element 
         # to the left_sum
         leftSum - = arr[i] 
   
         if (rightSum = = leftSum) :
             return i 
   
     # if it is not possible 
     # to split array into 
     # two parts.
     return - 1
   
# Prints two parts after 
# finding split point 
# using findSplitPoint()
def printTwoParts(arr, n) :
     splitPoint = findSplitPoint(arr, n)
   
     if (splitPoint = = - 1 or splitPoint = = n ) :
         print ( "Not Possible" ) 
         return
  
     for i in range ( 0 , n) :
         if (splitPoint = = i) :
             print ("")
         print (arr[i], end = " " )         
   
# Driver Code
arr = [ 1 , 2 , 3 , 4 , 5 , 5 ]
n = len (arr)
printTwoParts(arr, n)
   
# This code is contributed by Manish Shaw
# (manishshaw1)

C#

//C# program to split an array 
//into Two equal sum subarrays
using System;
   
class GFG {
   
     //Returns split point. If not possible, then
     //return -1.
     static int findSplitPoint( int []arr, int n)
     {
       
     //traverse array element and compute sum
     //of whole array
     int leftSum = 0;
       
     for ( int i = 0 ; i <n ; i++)
         leftSum += arr[i];
   
     //again traverse array and compute right 
     //sum and also check left_sum equal to 
     //right sum or not
     int rightSum = 0;
       
     for ( int i = n-1; i>= 0; i--)
     {
         //add current element to right_sum
         rightSum += arr[i];
   
         //exclude current element to the left_sum
         leftSum -= arr[i] ;
   
         if (rightSum == leftSum)
             return i ;
     }
   
     //if it is not possible to split array
     //into two parts.
     return -1;
     }
   
     //Prints two parts after finding split 
     //point using findSplitPoint()
     static void printTwoParts( int []arr, int n)
     {
         int splitPoint = findSplitPoint(arr, n);
       
         if (splitPoint == -1 || splitPoint == n )
         {
             Console.Write( "Not Possible" );
             return ;
         }
         for ( int i = 0; i <n; i++)
         {
             if (splitPoint == i)
                  Console.WriteLine();
                   
              Console.Write(arr[i] + " " );
         }
     }
   
     //Driver program
     public static void Main (String[] args) {
       
     int []arr = {1 , 2 , 3 , 4 , 5 , 5 };
     int n = arr.Length;
       
     printTwoParts(arr, n);
           
     }
}
   
//This code is contributed by parashar

PHP

<?php
//PHP program to split 
//an array into Two
//equal sum subarrays
  
//Returns split point. 
//If not possible, //then return -1.
function findSplitPoint( $arr , $n )
{
     //traverse array element and 
     //compute sum of whole array
     $leftSum = 0;
     for ( $i = 0 ; $i <$n ; $i ++)
         $leftSum += $arr [ $i ];
  
     //again traverse array and
     //compute right sum and also 
     //check left_sum equal to 
     //right sum or not
     $rightSum = 0;
     for ( $i = $n - 1; $i>= 0; $i --)
     {
         //add current element
         //to right_sum
         $rightSum += $arr [ $i ];
  
         //exclude current element 
         //to the left_sum
         $leftSum -= $arr [ $i ] ;
  
         if ( $rightSum == $leftSum )
             return $i ;
     }
  
     //if it is not possible 
     //to split array into 
     //two parts.
     return -1;
}
  
//Prints two parts after 
//finding split point 
//using findSplitPoint()
function printTwoParts( $arr , $n )
{
     $splitPoint = findSplitPoint( $arr , $n );
  
     if ( $splitPoint == -1 or 
         $splitPoint == $n )
     {
         echo "Not Possible" ;
         return ;
     }
     for ( $i = 0; $i <$n ; $i ++)
     {
         if ( $splitPoint == $i )
             echo "\n" ;
         echo $arr [ $i ] , " " ;
     }
}
  
//Driver Code
$arr = array (1, 2, 3, 4, 5, 5);
$n = count ( $arr );
printTwoParts( $arr , $n );
  
//This code is contributed by anuj_67.
?>

输出：

1 2 3 4
5 5

时间复杂度：O(n)

辅助空间：O(1)

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

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