确定数字数组是否可以分成两个数组，每个数组保持相同的数字总和 [英] Determine whether or not can an array of numbers can be divided into two arrays, with each array holding the same sum of numbers
问题描述
下面是一个代码，用于确定数字数组是否可以分为两个数组，每个数组都包含相同的数字总和。
例如：{1,3,2,6}可分为{6}和{1,2,3}，因此返回true
而{1,5,7}不能分为两个，平衡数组，因此返回false
Below is a code to determine whether or not can an array of numbers can be divided into two arrays, with each array holding the same sum of numbers. for example: {1, 3 ,2, 6} can be divided into {6} and {1,2,3}, therefore return true while {1,5,7} can't be divided into two, balanced array, therefore return false
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;
}
这是在codingbat练习的公认答案，我不明白这个特别是：
it's an accepted answer for an exercise in codingbat, I don't understand this piece in particular:
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。
doesn't for iteration usually starts with { and ends with } ? and how come if sum == 0 means it can be balanced? I have tried noting it down on piece of paper with array of {1,3,2,6} and had sum of 26, which returns false, where it's obvious that {1,3,2,6} should return true.
我认为我误读了代码，但我不知道哪些代码。或者算法可能是假的，但它在codingbat中被接受
I think I misread the code, I don't know which, though. Or maybe the algorithm is false, but it was accepted in codingbat
推荐答案
这两个for循环用于称量两个部分数组，找到数组的数组平衡点。
The two for-loops are for weighing the two parts of the array, to find the array balancing point of an array.
想象如下：
你有一个空的余额比例，在外部for循环的第一次迭代中，i为零。
You have a empty balance scale, in the first iteration of the outer for loop, i is zero.
它来到第一个for循环，这里j是0而i是0 i< j 为false，因此它不会进入第一个for-loop，而是进入第二个for-loop并从sum中减去所有数字。
It comes to first for loop, here j is 0 and i is 0 i < j is false, so it doesn't enter the first for-loop and it goes into the second for-loop and subtracts all the numbers from sum.
从外部for循环的第二次迭代开始，它开始进入第一个for循环，
开始逐个添加数组的元素到总和。
From second iteration onwards of the outer for-loop, it starts entering the first for-loop and starts adding the elements of the array one-by-one to the sum.
在图片中，它就像从空的天平刻度开始，将所有元素添加到第二个刻度中，并逐个元素移动到第一个刻度，如这个：
In pictures, it is like starting with an empty balance scale, adding all the elements into the second scale, and moving one by one element to the first scale, like this:
最后，如果总和为零，那么数组可以平衡，所以返回true。如果总和不是0，则它是不平衡的。
In the end, if the sum is zero, then the array can be balanced, so return true. If the sum isn't 0, it's unbalanced.
这些中的值由这样的循环平衡：
The values in the are balanced by the loops like this:
当i为0时外部for循环的迭代
循环2 - > i（0）j（0）减1，sum为-1
循环2 - > i（0）j（1）减3，求和-4
循环2 - > i（0）j（2）减2，求和-6
循环2 - > i（0）j（3）减去6，求和是-12
Iteration of outer for loop when i is 0
Loop 2 -> i(0) j(0) Subtract 1, sum is -1
Loop 2 -> i(0) j(1) Subtract 3, sum is -4
Loop 2 -> i(0) j(2) Subtract 2, sum is -6
Loop 2 -> i(0) j(3) Subtract 6, sum is -12
当i为1时外部for循环的迭代
循环1 - > i（1）j（0）加1，求和1
循环2 - > i（1）j（1）减3 ，sum是-2
循环2 - > i（1）j（2）减2，sum是-4
循环2 - > i（1）j（3）减去6，总和是-10
Iteration of outer for loop when i is 1
Loop 1 -> i(1) j(0) Add 1, sum is 1
Loop 2 -> i(1) j(1) Subtract 3, sum is -2
Loop 2 -> i(1) j(2) Subtract 2, sum is -4
Loop 2 -> i(1) j(3) Subtract 6, sum is -10
当我是2时外部for循环的迭代
循环1 - > i （2）j（0）加1，求和1
循环1 - > i（2）j（1）加3，求和4
循环2 - > i （2）j（2）减2，总和2
循环2 - > i（2）j（3）减6，总和为-4
Iteration of outer for loop when i is 2
Loop 1 -> i(2) j(0) Add 1, sum is 1
Loop 1 -> i(2) j(1) Add 3, sum is 4
Loop 2 -> i(2) j(2) Subtract 2, sum is 2
Loop 2 -> i(2) j(3) Subtract 6, sum is -4
外部的迭代当我是3时for循环
循环1 - > i（3）j（0）加1，求和1
循环1 - > i（3） j（1）加3，求和是4 $
循环1 - > i（3）j（2）加2，求和6
循环2 - > i（3） j（3）减去6，总和为0
Iteration of outer for loop when i is 3
Loop 1 -> i(3) j(0) Add 1, sum is 1
Loop 1 -> i(3) j(1) Add 3, sum is 4
Loop 1 -> i(3) j(2) Add 2, sum is 6
Loop 2 -> i(3) j(3) Subtract 6, sum is 0
最终结果为真，因此阵列可以平衡
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;
}
}
如果你想允许在数组的元素之间进行混洗，你可以使用如下的递归（注释是不言自明的）
If you want to allow shuffling between the elements of the array, you can use recursion as follows (comments are self-explanatory)
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);
}
}
这篇关于确定数字数组是否可以分成两个数组，每个数组保持相同的数字总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
