给定一个大于零的整数数组，找出是否可以将其拆分为两个子数组（无需对元素重新排序），从而使两个子数组之和相同。打印两个子阵列。 例如：
null
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
被问到： Facebook采访
A. 简单解决方案 是运行两个循环来拆分数组，并检查是否可以将数组拆分为两部分，使第一部分的和等于第二部分的和。 下面是上述想法的实现。
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 "" ; 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. ?> |
Javascript
<script> // Java script program to split an array // into two equal sum subarrays // Returns split point. If // not possible, then return -1. function findSplitPoint(arr,n) { let leftSum = 0 ; // traverse array element for (let i = 0; i < n; i++) { // add current element to left Sum leftSum += arr[i] ; // find sum of rest array // elements (rightSum) let rightSum = 0 ; for (let 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) { let splitPoint = findSplitPoint(arr, n); if (splitPoint == -1 || splitPoint == n ) { document.write( "Not Possible" ); return ; } for (let i = 0; i < n; i++) { if (splitPoint == i) document.write( "<br>" ); document.write(arr[i] + " " ); } } // Driver program let arr = [1 , 2 , 3 , 4 , 5 , 5 ]; let n = arr.length; printTwoParts(arr, n); // contributed by sravan kumar </script> |
输出：
1 2 3 45 5
时间复杂度：O（n） 2. ) 辅助空间：O（1） 一 有效解决方案 首先从左到右计算整个数组的和。现在我们从右边遍历数组并跟踪右和，左和可以通过从整个和中减去当前元素来计算。 下面是上述想法的实现。
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 "" ; 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. ?> |
Javascript
<script> // Javascript 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 let leftSum = 0; for (let 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 let rightSum = 0; for (let 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) { let splitPoint = findSplitPoint(arr, n); if (splitPoint == -1 || splitPoint == n ) { document.write( "Not Possible" ); return ; } for (let i = 0; i < n; i++) { if (splitPoint == i) document.write( "</br>" ); document.write(arr[i] + " " ); } } let arr = [1 , 2 , 3 , 4 , 5 , 5 ]; let n = arr.length; printTwoParts(arr, n); // This code is contributed by rameshtravel07. </script> |
输出：
1 2 3 45 5
时间复杂性： O（n） 辅助空间： O（1） 本文由 尼桑·辛格 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
