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

Question

下面是一个代码,用于确定数字数组是否可以分为两个数组,每个数组都包含相同的数字总和.例如:{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循环用于称量阵列的两个部分,以找到阵列的阵列平衡点.

可以这样想:

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

它来到第一个for循环,这里j是0而i是0 i < j是假的,所以它不进入第一个for循环,它进入第二个for循环并从sum中减去所有数字.

从外部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,sum为1
循环1 - > i(2)j(1)加3,sum为4
循环2 - > i (2)j(2)减2,求和2
循环2 - > i(2)j(3)减6,求和-4

当i为3时,外部for循环的迭代
循环1 - > i(3)j(0)加1,sum为1
循环1 - > i(3)j(1)加3,sum为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); 
    }

}