要求給定一個(gè)數(shù)組，獲取數(shù)組的一個(gè)分界點(diǎn)的下標(biāo)，使得該分界點(diǎn)的兩側(cè)子數(shù)組的和相等。如果存在多個(gè)分界點(diǎn)，只返回第一個(gè)分界點(diǎn)的下標(biāo)，如果沒(méi)有則返回-1。
要求：時(shí)間復(fù)雜度不得超過(guò)O(n)。

測(cè)試用例：

輸入：[-20, 30, 10, 40, 20]
返回：3

分析：正常的計(jì)算思路應(yīng)該是，用一個(gè)index標(biāo)記當(dāng)前計(jì)算的下標(biāo)，從數(shù)組第二個(gè)元素（即index為1開(kāi)始）開(kāi)始計(jì)算，將這個(gè)元素左邊的相加求和，然后右邊相加求和，對(duì)比是否相等。然后index++依次遍歷，知道index 遍歷到數(shù)組倒數(shù)第二個(gè)元素，都沒(méi)有找到則返回-1。

Java實(shí)現(xiàn)

按照上面的思路，最直接的算法為：

    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;
    }

復(fù)雜度分析：
首先最外層參數(shù)為 i 的for循環(huán)遍歷取決于數(shù)組數(shù)據(jù)大小，數(shù)組長(zhǎng)度為n則最大需要 n - 2 次運(yùn)算。
外層for循環(huán)內(nèi)部的兩個(gè)for循環(huán)的 j + k 最大循環(huán)次數(shù)實(shí)際等于 n - 1。
所以最終：(n - 2)(n - 1) 復(fù)雜度為O(n^2)，不符合算法要求。

那么我們需要優(yōu)化的就是如何降低復(fù)雜度，先思考，為什么會(huì)出現(xiàn)這么高的時(shí)間復(fù)雜度。大多數(shù)做計(jì)算對(duì)比的算法復(fù)雜度過(guò)高都是因?yàn)樽隽酥貜?fù)性的運(yùn)算，我們看一下之前的算法并模擬一下計(jì)算的過(guò)程
先模擬一下leftSum的計(jì)算：
當(dāng)i == 1 時(shí)，leftSum += array[0]
當(dāng)i == 2時(shí)，leftSum += array[0]、leftSum += array[1]
當(dāng)i == 3時(shí)，leftSum += array[0]、leftSum += array[1]、leftSum += array[2]
在看一下rightSum的計(jì)算：
當(dāng)i == 1 時(shí)，rightSum += array[2]、rightSum += array[3]、rightSum += array[4]
當(dāng)i == 2時(shí)，rightSum += array[3]、rightSum += array[4]
當(dāng)i == 3時(shí)，rightSum += array[4]
是不是發(fā)現(xiàn)問(wèn)題了，實(shí)際上最外層的for循環(huán)內(nèi)部計(jì)算 leftSum和rightSum進(jìn)行了大量的重復(fù)計(jì)算，當(dāng)i == 3時(shí)，leftSum還是將數(shù)組的第0、1、2元素累加，但是之前i==2時(shí)，數(shù)組的第0、1元素已經(jīng)做過(guò)一次加法了，那么第一步加法就是多余的，rightSum的計(jì)算同理。

既然發(fā)現(xiàn)了問(wèn)題所在，就是怎么優(yōu)化掉重復(fù)的加法問(wèn)題了?，F(xiàn)在換一種思維方式：
開(kāi)始需要比較的是array數(shù)組下標(biāo)為1的元素，這時(shí)如果知道了整個(gè)數(shù)組的和為allSum。那么左邊子數(shù)組的和leftSum就是array的第一個(gè)元素array[0]。右邊的子數(shù)組的和就是rightSum = allSum - leftSum - array[1]；
當(dāng)下一次index2時(shí)，將上一次計(jì)算的leftSum用于下一次比較，leftSum只需要再加上array[1]，就是左邊數(shù)組的和，而右邊的子數(shù)組的和還可以通過(guò)rightSum = allSum - leftSum - array[1]計(jì)算。
這樣的話，左側(cè)數(shù)組和只需要每次累加一個(gè)新的需要對(duì)比的元素，右側(cè)直接就可以通過(guò)減法計(jì)算不需要累加：

    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;
    }

復(fù)雜度分析：第一個(gè)for循環(huán)計(jì)算allSum取決于數(shù)組容量n，后面for循環(huán)計(jì)算最多需要計(jì)算 n - 2 次，最多需要 2n - 2，時(shí)間復(fù)雜度為 O(n)。

使用包含20萬(wàn)條長(zhǎng)度數(shù)據(jù)的數(shù)組，測(cè)試優(yōu)化后前后時(shí)間對(duì)比：

        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));
            }
        });

優(yōu)化前

【Midde】
開(kāi)始：16:08:22.262
100000
結(jié)束：16:08:34.178
耗時(shí)：11.916秒
-------------------------------------

優(yōu)化后

【Midde】
開(kāi)始：16:10:12.414
100000
結(jié)束：16:10:12.425
耗時(shí)：0.01秒
-------------------------------------

Objective-C實(shí)現(xiàn)

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;
    }
    // 復(fù)雜度 2n - 2 => O(n)
    return -1;
}

總結(jié)

這個(gè)算法題主要就是考察思維邏輯的，并沒(méi)有對(duì)數(shù)據(jù)結(jié)構(gòu)的知識(shí)進(jìn)行深入考察，即便不清楚數(shù)組查找的復(fù)雜度為O(1)，也不會(huì)出現(xiàn)錯(cuò)誤，只需要靈活思考就能夠解決，屬于簡(jiǎn)單的問(wèn)題。