对于数组，请检查是否存在索引，其中左侧的元素和等于其右侧元素的和。

Question

问题

扩展自这个黑客等级问题。

给定长度为A的数组n，确定数组中是否存在一个元素，使其左侧的元素之和等于其右侧元素的和。如果左边/右边没有元素，则将之和视为零。

例如，[ 1, 1, 1, 2 ]，索引2的左边和右边的元素之和相等。

逼近

下面是对值数组从左到右的计算的描述。在我的实现中，我在同一个循环中做左到右和右到左的评估.

1. 给定一个值数组，从第一个和最后一个索引开始。这些是左、右和的初始值，以及左、右指数的初始值。
2. 用1增加左索引，用1 减少右索引
   1. 如果左索引小于右索引，则将右侧索引的值添加到右和。
   2. 如果左索引大于右索引，则从右和减去左索引处的值。
   3. 如果左和右和是相同的，那么return就提前
   4. 否则，将左侧索引处的值添加到左和。

3. 退出循环后，检查左和是否等于右和。

Implementation

public class BalancedArraySumIdentifier {
    public static boolean isBalanced(int[] values) {
        int leftToRightLeftSum = 0;
        int leftToRightRightSum = 0;

        int rightToLeftRightSum = 0;
        int rightToLeftLeftSum = 0;

        for (int i = 0; i < values.length; i++) {
            int j = values.length - 1 - i;

            if (i < j) {
                leftToRightRightSum += values[j];
                rightToLeftLeftSum += values[i];
            } else if (i > j) {
                leftToRightRightSum -= values[i];
                rightToLeftLeftSum -= values[j];
            }

            if (leftToRightLeftSum == leftToRightRightSum || rightToLeftLeftSum == rightToLeftRightSum) {
                return true;
            }

            leftToRightLeftSum += values[i];
            rightToLeftRightSum += values[j];
        }

        return leftToRightLeftSum == leftToRightRightSum || rightToLeftLeftSum == rightToLeftRightSum;
    }
}

Answer 1

首先，我认为您的最后一条return语句是不正确的:就我所能得出的结果而言，它将数组号的总和与0进行比较，这与问题无关，它会导致程序输出像[-1,1]或[1,2,-3]这样的数组的true。

另外，正如您已经在JS1's观察的帮助下发现的那样，leftToRightRightSum和rightToLeftLeftSum只包含一次i >= j - 1的有效值，或者，换句话说，一旦数组中的每个数字被至少两个指针中的一个迭代过一次。同样，一旦这两个变量包含有效值，两个指针再次迭代数组中的每个数字，以检查其中一个是否满足任务中规定的条件。

因此，您的两个指针只是将可以由一个指针完成的工作除以:计算数字的总和(第一个数组迭代)，然后遍历数组并将每个元素的总和分为左和右和(第二次数组迭代)。这看起来可能更多的工作，因为就代码而言，它需要两次迭代，而您的代码只需要一次迭代，但是另一方面，由于存在两个指针变量，您的代码在每个迭代循环中所做的工作要比这个算法所做的工作要多，因此，我想性能上不会有太大的差异。

public static boolean isBalanced(int[] values) {
    int totalSum = Arrays.stream(values).sum(); // first "iteration"

    for (int i = 0, leftSum = 0, rightSum = totalSum;
            i < values.length;
            i++) { //second iteration
        rightSum -= values[i];
        if (leftSum == rightSum) {
            return true;
        }
        leftSum += values[i];
    }

    return false;
}

Answer 2

这可能需要获取数组的每个索引，并检查左和右之和是否相等，如果考虑到这一点，左和右之间的差值必须为0(左-右=0)。所以我们可以先取总和，减去0的索引值，然后检查它是否等于0。如果没有，则向左求和0索引，并从总和减去它，这意味着总和变为右和。接下来，减去总数中的1指数(现在它充当右和)，并检查它是否等于左和。如果不是，数组将一直这样做，直到它的<数组长度。

此外，您可以自定义函数返回整数，以便准确确定哪个索引确实返回。

public static boolean isBalanced(int[] values){
    int totalSum=0;
    for(int i=0;i<values.length;i++){
        totalSum+=values[i];
    }
    int leftSum=0;
    for(int i=0;i<values.length;i++){
        totalSum-=values[i];
        if(leftSum==totalSum)
        return true;
        leftSum+=values[i];
    }
    return false;
}