确定一个数字数组是否可以分成两个数组,每个数组包含相同的数字总和

2022-01-24 00:00:00 loops iteration java

下面是一个代码,用于确定一个数字数组是否可以分成两个数组,每个数组包含相同的数字总和.例如:{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 为假,所以它不会进入第一个 for 循环,而是进入第二个 for 循环并从 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,和为-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,和为-2
循环 2 ->i(1) j(2) 减2,和为-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

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

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

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

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("
Final result is "+canBalance(test));
    }

    public static boolean canBalance(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            System.out.println("
Iteration 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); 
    }

}

相关文章