下面是一段代码,用于确定一个数字数组是否可以分为两个数组,每个数组包含相同的数字总和。 例如:{1, 3 ,2, 6}可以分为{6}和{1,2,3},因此返回true 而{1,5,7}不能一分为二,平衡数组,所以返回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 练习的公认答案,我不是特别理解这篇文章:
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中被接受了
最佳答案
这两个 for 循环用于权衡数组的两个部分,找到数组的数组平衡点。
可以这样想:
你有一个空天平,在外层 for 循环的第一次迭代中,i 为零。
首先是for循环,这里j为0,i为0 i < j
为假,因此它不会进入第一个 for 循环,而是进入第二个 for 循环并从总和中减去所有数字。
从外层 for 循环的第二次迭代开始,它开始进入第一个 for 循环并且 开始将数组的元素一个一个地添加到总和中。
在图片中,就像是从一个空的天平秤开始,将所有元素添加到第二个秤中,然后将一个元素一个一个地移动到第一个秤上,就像这样:
最后,如果和为零,则数组可以平衡,所以返回true。如果总和不为 0,则它是不平衡的。
中的值由这样的循环平衡:
当i为0时外层for循环的迭代
循环2 -> i(0) j(0) 减1,和为-1
循环2 -> i(0) j(1) 减3,和为-4
循环2 -> i(0) j(2) 减2,和为-6
循环2 -> i(0) j(3) 减6,和为-12
当i为1时外层for循环的迭代
循环1 -> i(1) j(0) 加1,和为1
循环2 -> i(1) j(1) 减3,和为-2
循环2 -> i(1) j(2) 减2,和为-4
循环2 -> i(1) j(3) 减6,和为-10
当i为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
当i为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
最终结果为真,因此数组可以平衡
代码:
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);
}
}
关于java - 确定一个数字数组是否可以分为两个数组,每个数组包含相同的数字总和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25967177/