确定数字数组是否可以分成两个数组，每个数组保持相同的数字总和

下面是一个代码，用于确定数字数组是否可以分为两个数组，每个数组都包含相同的数字总和。 例如：{1,3,2,6}可以分为{6}和{1,2,3}，因此返回true而{1,5,7}不能分为两个，平衡数组，因此返回虚假

public boolean canBalance(int[] nums) { for (int i = 0; i < nums.length; i++) { int sum = 0; for (int j = 0; j < i; j++) sum += nums[j]; for (int j = i; j < nums.length; j++) sum -= nums[j]; if (sum == 0) return true; } return false; } 

这是一个接受的编码运动的答案，我特别不理解这篇文章：

 for (int j = 0; j < i; j++) sum += nums[j]; for (int j = i; j < nums.length; j++) sum -= nums[j]; 

不用于迭代通常以{并以}结尾？ 如果sum == 0意味着它可以平衡怎么来？ 我已经尝试用{1,3,2,6}的数组在纸上记下它，并且总和为26，返回false，显然{1,3,2,6}应该返回true。

我想我误解了代码，但我不知道哪些代码。 或者算法可能是假的，但它在codingbat中被接受

Answer 1

两个for循环用于称量arrays的两个部分，以找到arrays的arrays平衡点 。

想想这样：

你有一个空的余额比例，在外部for循环的第一次迭代中，i为零。

首先是for循环，这里j是0而i是0 i < j是false， 所以它不进入第一个for循环，它进入第二个for循环并从sum中减去所有数字。

从外部for循环的第二次迭代开始，它开始进入第一个for循环，并开始逐个添加数组的元素到总和。

在图片中，它就像从空的天平刻度开始，将所有元素添加到第二个刻度中，并逐个元素移动到第一个刻度，如下所示：

最后，如果总和为零，则数组可以平衡，因此返回true。 如果总和不是0，则它是不平衡的。

这里的值由这样的循环平衡：

当i为0时迭代外部for循环
循环2 - > i（0）j（0）减1，sum为-1
循环2 - > i（0）j（1）减3，总和为-4
循环2 - > i（0）j（2）减去2，sum为-6
循环2 - > i（0）j（3）减去6，sum为-12

当我为1时迭代外部for循环
循环1 - > i（1）j（0）加1，sum为1
循环2 - > i（1）j（1）减3，总和为-2
循环2 - > i（1）j（2）减2，总和为-4
循环2 - > i（1）j（3）减去6，总和为-10

当我是2时迭代外部for循环
循环1 - > i（2）j（0）加1，sum为1
循环1 - > i（2）j（1）加3，sum为4
循环2 - > i（2）j（2）减2，总和2
循环2 - > i（2）j（3）减去6，总和为-4

当我是3时迭代外部for循环
循环1 - > i（3）j（0）加1，sum为1
循环1 - > i（3）j（1）加3，sum为4
循环1 - > i（3）j（2）加2，sum为6
循环2 - > i（3）j（3）减去6，sum为0

最终结果是正确的，因此arrays可以平衡

码：

 public class Test { public static void main(String[] args) { int[] test = { 1, 3, 2, 6 }; System.out.println("\nFinal result is "+canBalance(test)); } public static boolean canBalance(int[] nums) { for (int i = 0; i < nums.length; i++) { System.out.println("\nIteration of outer for loop when i is " + i); int sum = 0; for (int j = 0; j < i; j++){ sum += nums[j]; System.out.println("Loop 1 -> i(" +i + ") j("+j + ") Add "+nums[j] + ", sum is "+sum+" "); } for (int j = i; j < nums.length; j++){ sum -= nums[j]; System.out.println("Loop 2 -> i(" +i + ") j("+j + ") Subtract "+nums[j] + ", sum is "+sum+" "); } if (sum == 0) return true; } return false; } } 

---

如果要允许在数组元素之间进行混洗，可以按如下方式使用递归（注释不言自明）

 public class Test { public static void main(String[] args) { int[] original = { 10, 2, 24, 32 }; System.out.println(canDivideArray(original)); } private static boolean canDivideArray(int[] originalArray) { int total = 0; for (int number : originalArray) { total += number; } // check if sum == 2x for any value of x if (total % 2 != 0) { return false; } else { // sum of each half array should be x total /= 2; } return isTotal(originalArray, originalArray.length, total); } private static boolean isTotal(int array[], int n, int total) { // successful termination condition if (total == 0) { return true; } // unsuccessful termination when elements have finished but total is not reached if (n == 0 && total != 0){ return false; } // When last element is greater than total if (array[n - 1] > total) return isTotal(array, n - 1, total); //check if total can be obtained excluding the last element or including the last element return isTotal(array, n - 1, total - array[n - 1]) || isTotal(array, n - 1, total); } } 

Answer 2

如果不允许对数组元素进行重新排序，我们只需在给定数组中找到分割点。 问题中的解决方案是通过尝试所有可能的分裂点并检查两个部分的总和是否相等来做到这一点。 它具有输入数组长度的二次方。

请注意，很容易想出具有线性工作的解决方案，例如以下代码段。 它在数组的左侧和右侧构建元素的总和，在每个步骤中，通过添加数组元素来增加较小的和。 重复这一过程直到部件相遇。

这假设数组不包含任何负数。

 public boolean canBalance(int[] nums) { int sumL = 0, sumR = 0; int l = -1, r = nums.length; while (r - l > 1) { if (sumL < sumR) { sumL += nums[++l]; } else { sumR += nums[--r]; } } return sumL == sumR; } 

Answer 3

这是该问题的递归解决方案，一个非递归解决方案可以使用辅助方法将索引0的总和获取到for循环中的当前索引，另一个可以使用相同当前索引的所有元素的总和结束，这是有效的。 现在，如果你想将元素放入一个数组并比较总和，首先找到标记溢出的点（索引），其中两边的总和相等，然后得到一个列表并在该索引之前添加值，另一个列表去在那个指数之后。

这是我的（递归），它只确定是否有一个分割数组的位置，以便一边的数字总和等于另一边的数字之和。 担心indexOutOfBounds，这很容易在递归中发生，一个轻微的错误可能会导致致命并产生大量exception和错误。

 public boolean canBalance(int[] nums) { return (nums.length <= 1) ? false : canBalanceRecur(nums, 0); } public boolean canBalanceRecur(int[] nums, int index){ //recursive version if(index == nums.length - 1 && recurSumBeforeIndex(nums, 0, index) != sumAfterIndex(nums, index)){ //if we get here and its still bad return false; } if(recurSumBeforeIndex(nums, 0, index + 1) == sumAfterIndex(nums, index + 1)){ return true; } return canBalanceRecur(nums, index + 1); //move the index up } public int recurSumBeforeIndex(int[] nums, int start, int index){ return (start == index - 1 && start < nums.length) ? nums[start] : nums[start] + recurSumBeforeIndex(nums, start + 1, index); } public int sumAfterIndex(int[] nums, int startIndex){ return (startIndex == nums.length - 1) ? nums[nums.length - 1] : nums[startIndex] + sumAfterIndex(nums, startIndex + 1); } 

//非递归

 public boolean canBalance(int[] nums) { for(int a = 0; a < nums.length; a++) { int leftSum = 0; int rightSum = 0; for(int b = 0; b < a; b++) { leftSum += nums[b]; } for(int c = a; c < nums.length; c++) { rightSum += nums[c]; } if(leftSum == rightSum) { return true; } } return false; } 

Answer 4

我想在原始问题中“划分”不允许重新排序数组。 因此，您只需在特定位置打破arrays，我们将拥有arrays的左侧和右侧。 每一边的数字应该相同。

外环的索引（i）是断开位置。

 for (int i = 0; i < nums.length; i++) { 

第一个内部循环对数组的左侧求和。

 for (int j = 0; j < i; j++) sum += nums[j]; 

第二个内环从左侧数组的总和中减去右侧的元素。

 for (int j = i; j < nums.length; j++) sum -= nums[j]; 

如果最终结果为零，则表示左侧和右侧的总和相同。 否则，继续外循环并检查其他断开位置，直到找到正确的断开位置。

Answer 5

使用DP解决方案解决此问题。

//创建一个2D数组并以自下而上的方式填充// DP [totalsum / 2 + 1] [数组的长度+]

 bool divisible(int arr[], int size) { int sum = 0; // Determine the sum for (i = 0; i < size; i++) sum += arr[i]; if (sum%2 != 0) return false; bool DP[sum/2+1][size+1]; // initialize top row as true for (i = 0; i <= size; i++) DP[0][i] = true; // initialize leftmost column, except DP[0][0], as 0 for (i = 1; i <= sum/2; i++) DP[i][0] = false; // Fill the partition table in botton up manner for (int i = 1; i <= sum/2; i++) { for (int j = 1; j <= size; j++) { DP[i][j] = DP[i][j-1]; if (i >= arr[j-1]) DP[i][j] = DP[i][j] || DP[i - arr[j-1]][j-1]; } } return DP[sum/2][size]; } 

Answer 6

正如@Alvin Bunk在评论中所说，你在问题中给出的答案本身并不是一个好的答案，即使元素的顺序在数组中发生了变化，它的工作方式也不同。

你应该查看这个wiki理论并实现它： http ： //en.wikipedia.org/wiki/Partition_problem

Answer 7

我写了一个独立的方法来对数组的各个部分求和，并在我的解决方案中使用它来获得我能看到的最简单的方法。 如果有人有任何意见，请加入。我感谢您的评论。

 //Create a method that gets the sum from start to the iteration before end. public int sumArray (int[] nums, int start, int end) { //Create a sum int that tracks the sum. int returnSum = 0; //Add the values from start (inclusive) to end (exclusive). In other words i : [start, end) for (int i = start; i < end; i++) { returnSum += nums[i]; } return returnSum; } //This is our main class. public boolean canBalance(int[] nums) { //If nums has an actual value, we can work with it. if (nums.length > 0) { //We check to see if there is a value that is equal by using the sumArray method. for (int i = 0; i < nums.length; i++) { //If from [0,i) the value equals from [i, nums.length), we return true; if (sumArray(nums, 0, i) == sumArray(nums, i, nums.length)) { return true; } } //If we finish the loop, and find nothing, we return false; return false; } //If there is no value, we return false. else { return false; } } 

Answer 8

如果在Java中的for语句之后代码周围没有任何花括号，则下一行是作为for语句的一部分处理的唯一行。 在这种情况下，for就像一个调用下一​​行代码的函数，这是一个for语句，然后调用下一行代码。 所以第一个用于调用第二个，用于评估双方是否相同，如果它们不是那么它又回到第二个，继续递增直到它完成然后它返回到第一个，增加，并调用第二个…等等。 但是，这段代码似乎已经部分破坏了，因为它必须按照数字顺序排列所有数字，并且它不会检查中间的任何内容。

例如：
{1, 2, 3, 1} //evaluates to true because 1-1=0, although it should be false
{6, 2, 2, 3} //evaluates to true because 6-3-2=0, although it should be false
{2, 3, 4, 6} //evaluates to true because 2+3-6=0, although it should be false