要求给定一个数组，获取数组的一个分界点的下标，使得该分界点的两侧子数组的和相等。如果存在多个分界点，只返回第一个分界点的下标，如果没有则返回-1。
要求：时间复杂度不得超过O(n)。
测试用例：
输入：[-20, 30, 10, 40, 20]
返回：3
分析：正常的计算思路应该是，用一个index标记当前计算的下标，从数组第二个元素（即index为1开始）开始计算，将这个元素左边的相加求和，然后右边相加求和，对比是否相等。然后index++依次遍历，知道index 遍历到数组倒数第二个元素，都没有找到则返回-1。
Java实现
按照上面的思路，最直接的算法为：
static int middleIndexWithArray(Integer[] array) {
if (array.length < 3) return -1;
for (int i = 1; i < array.length - 1; i++) {
int leftSum = 0;
int rightSum = 0;
for (int j = 0; j < i; j++) {
leftSum += array[j];
}
for (int k = i + 1; k < array.length; k++) {
rightSum += array[k];
}
if (leftSum == rightSum) {
return i;
}
}
return - 1;
}
复杂度分析：
首先最外层参数为 i 的for循环遍历取决于数组数据大小，数组长度为n则最大需要 n - 2 次运算。
外层for循环内部的两个for循环的 j + k 最大循环次数实际等于 n - 1。
所以最终：(n - 2)(n - 1) 复杂度为O(n^2)，不符合算法要求。
那么我们需要优化的就是如何降低复杂度，先思考，为什么会出现这么高的时间复杂度。大多数做计算对比的算法复杂度过高都是因为做了重复性的运算，我们看一下之前的算法并模拟一下计算的过程
先模拟一下leftSum的计算：
当i == 1 时，leftSum += array[0]
当i == 2时，leftSum += array[0]、leftSum += array[1]
当i == 3时，leftSum += array[0]、leftSum += array[1]、leftSum += array[2]
在看一下rightSum的计算：
当i == 1 时，rightSum += array[2]、rightSum += array[3]、rightSum += array[4]
当i == 2时，rightSum += array[3]、rightSum += array[4]
当i == 3时，rightSum += array[4]
是不是发现问题了，实际上最外层的for循环内部计算 leftSum和rightSum进行了大量的重复计算，当i == 3时，leftSum还是将数组的第0、1、2元素累加，但是之前i==2时，数组的第0、1元素已经做过一次加法了，那么第一步加法就是多余的，rightSum的计算同理。
既然发现了问题所在，就是怎么优化掉重复的加法问题了。现在换一种思维方式：
开始需要比较的是array数组下标为1的元素，这时如果知道了整个数组的和为allSum。那么左边子数组的和leftSum就是array的第一个元素array[0]。右边的子数组的和就是rightSum = allSum - leftSum - array[1]；
当下一次index2时，将上一次计算的leftSum用于下一次比较，leftSum只需要再加上array[1]，就是左边数组的和，而右边的子数组的和还可以通过rightSum = allSum - leftSum - array[1]计算。
这样的话，左侧数组和只需要每次累加一个新的需要对比的元素，右侧直接就可以通过减法计算不需要累加：
static int middleIndexWithArray(Integer[] array) {
if (array.length < 3) return -1;
int allSum = 0;
int leftSum = 0;
int rightSum = 0;
for (int i = 0; i < array.length; i++) {
allSum += array[i];
}
for (int i = 1; i < array.length - 1; i++) {
leftSum += array[i - 1].intValue();
rightSum = allSum - leftSum - array[i].intValue();
if (leftSum == rightSum) return i;
}
return -1;
}
复杂度分析：第一个for循环计算allSum取决于数组容量n，后面for循环计算最多需要计算 n - 2 次，最多需要 2n - 2，时间复杂度为 O(n)。
使用包含20万条长度数据的数组，测试优化后前后时间对比：
TimeTool.check("Midde", new Task() {
public void execute() {
Integer[] array = new Integer[200001];
for (int i = 0; i < 200001; i++) {
if (i < 100000) {
array[i] = i;
} else if (i == 100000) {
array[i] = -1;
} else {
array[i] = 200000 - i;
}
}
System.out.println(middleIndexWithArray(array));
}
});
优化前
【Midde】
开始：16:08:22.262
100000
结束：16:08:34.178
耗时：11.916秒
-------------------------------------
优化后
【Midde】
开始：16:10:12.414
100000
结束：16:10:12.425
耗时：0.01秒
-------------------------------------
Objective-C实现
NSInteger middleIndexWithArray(NSArray<NSNumber *> * array) {
if (array.count < 3) return -1;
NSInteger leftSum = 0;
NSInteger rightSum = 0;
NSInteger allSum = 0;
// n
for (NSNumber *sum in array) allSum += sum.integerValue;
// max: n - 2
for (NSInteger i = 1; i < array.count - 1; i++) {
leftSum += array[i - 1].integerValue;
rightSum = allSum - leftSum - array[i].integerValue;
if (leftSum == rightSum) return i;
}
// 复杂度 2n - 2 => O(n)
return -1;
}
总结
这个算法题主要就是考察思维逻辑的，并没有对数据结构的知识进行深入考察，即便不清楚数组查找的复杂度为O(1)，也不会出现错误，只需要灵活思考就能够解决，属于简单的问题。
网友评论