java - 给定的零索引数组 & 该数组的平衡索引

标签 java c++ arrays algorithm data-structures

<分区>

给出了一个由 N 个整数组成的零索引数组 A。该数组的平衡索引是任意整数 P，满足 0 ≤ P < N 且较低索引元素的总和等于较高索引元素的总和，即 A[0] + A[1] + ... + A[P−1] = A[P+1] + ... + A[N−2] + A[N−1]。假定零元素之和等于 0。如果 P = 0 或 P = N−1，则可能发生这种情况。

例如，考虑以下由 N = 8 个元素组成的数组 A:

  A[0] = -1
  A[1] =  3
  A[2] = -4
  A[3] =  5
  A[4] =  1
  A[5] = -6
  A[6] =  2
  A[7] =  1

P = 1 是这个数组的平衡索引，因为:

A[0] = −1 = A[2] + A[3] + A[4] + A[5] + A[6] + A[7]

P = 3 是这个数组的平衡索引，因为:

A[0] + A[1] + A[2] = −2 = A[4] + A[5] + A[6] + A[7]

P = 7 也是一个均衡指数，因为:

A[0] + A[1] + A[2] + A[3] + A[4] + A[5] + A[6] = 0

并且没有索引大于 7 的元素。

P = 8 不是均衡指数，因为它不满足条件 0 ≤ P < N。

现在我必须写一个函数:

int solution(int A[], int N);

给定一个由 N 个整数组成的零索引数组 A，返回它的任何平衡索引。如果不存在均衡指标，该函数应返回-1。

例如，给定上面所示的数组 A，函数可能会返回 1、3 或 7，如上所述。

假设:

N is an integer within the range [0..100,000];
each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

这里有一些复杂性:

Elements of input arrays can be modified.

最佳答案

100% - Java

int solution(int A[], int N) {

    long sum = 0;
    for (int i = 0; i < A.length; i++) {
        sum += (long) A[i];
    }
    long leftSum = 0;
    long rightSum = 0;

    for (int i = 0; i < A.length; i++) {
        rightSum = sum - (leftSum + A[i]);
        if (leftSum == rightSum) {
            return i;
        }
        leftSum += A[i];
    }
    return -1;
}

关于java - 给定的零索引数组 & 该数组的平衡索引，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33375769/

上一篇：c++ - 为什么我们不能泛化指针声明？

下一篇：c++ - #define 和创建普通类型有什么区别？

相关文章：

java - 使用子字符串的数组中元素的索引

c++ - 监视器和条件变量，它们是一样的吗？

java - 数组中的元素，使得其左侧元素的总和等于其右侧元素的总和

java - 使用 Spring MVC 的 XML View

java - 断言无法解决

java - 递归函数单独工作正常，但一起导致堆栈溢出错误

java - 违反外键约束

c# - 将整数发送到 Android 后台应用程序

c++ - 为什么我的 ifstream 中出现无限循环？

ios - 如何快速创建 3D 数组/矩阵？