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

本文概述

C++
Java
Python3
C#
PHP
C++
Java
Python3
C#
PHP

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

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 programpublic 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" ) returnfor 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# 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" ) returnfor 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# 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. ?>

输出：