确定数字数组是否可以分成两个数组,每个数组保持相同的数字总和 [英] 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屋!