2017阿裡算法程式設計題--數組分片問題

對于一個長度為N的整型數組A， 數組裡所有的數都是正整數，對于兩個滿足

0<=X <= Y <N

的整數，A[X], A[X+1] … A[Y]構成A的一個切片，記作(X, Y)。

用三個下标 m1, m2, m3下标滿足條件

0 < m1, m1 + 1 < m2, m2 +1 < m3 < N – 1

。

可以把這個整型數組分成(0, m1-1), (m1+1, m2-1), (m2+1, m3-1), (m3+1, N-1) 四個切片。如果這四個切片中的整數求和相等，稱作“四等分”。

編寫一個函數，求一個給定的整型數組是否可以四等分，如果可以，傳回一個布爾類型的true，如果不可以傳回一個布爾類型的false。

限制條件： 數組A最多有1,000,000項，數組中的整數取值範圍介于-1,000,000到1,000,000之間。

要求： 函數的計算複雜度為O(N)，使用的額外存儲空間（除了輸入的數組之外）最多為O(N)。

例子：

對于數組A=[2, 5, 1, 1, 1, 1, 4, 1, 7, 3, 7] 存在下标 2, 7, 9使得數組分成四個分片[2, 5], [1, 1, 1, 4], [7], [7]，這三個分片内整數之和相等，是以對于這個數組，函數應該傳回true。

對于數組 A=[10, 2, 11, 13, 1, 1, 1, 1, 1]， 找不到能把數組四等分的下标，是以函數應該傳回false。

解法一：

package ali;

public class Fourarr2 {

    static boolean resolve(int[] a) {

        if (a == null || a.length < )
            return false;

        // 定義兩個個index
        int i = ;
        int j = a.length - ;
        int mid = ;
        // 自定義三個變量, suml 和 sumr分别表示兩邊的和, suma表示最後的結果和
        int suma = , sumb = , suml = , sumr = ;
        // 初值
        suml += a[i];
        sumr += a[j];
        while (i < j) {
            // 左邊i自加
            if (suml < sumr) {
                i++;
                suml += a[i];
            } else if (suml > sumr) {// 右邊j自減
                j--;
                sumr += a[j];
            } else {// suml==sumr
                mid = Math.max(mid, i + );
                suma = ;
                sumb = ;
                while (mid < j - ) {
                    suma += a[mid];
                    if (suma == suml) {
                        mid += ;
                        while (mid < j - ) {
                            sumb += a[mid];
                            if (sumb == suma && mid +  == j)
                                return true;
                            else if (sumb < suml)
                                mid++;
                            else
                                break;
                        }
                        break;
                    } else if (suma < suml)
                        mid++;
                    else {
                        i++;
                        suml += a[i];
                        break;
                    }
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        // int[] a = { 1, 1, 1, 1, 5, 4, 6, 4, 5, 1, 3 };
        // int[] a = { 1, 1, 1, 4, 4, 6, 4, 1, 3 };
        // int[] a = { 2, 5, 1, 1, 1, 1, 4, 1, 7, 3, 7 }; // true
        int[] a = { , , , , , , ,  }; // true
        int[] a1 = { , , , , , , ,  }; // false
        int[] a2 = { , , , , , , , ,  }; // true

        System.out.println(resolve(a));
    }
}
           

解法二：

package ali;

public class FourArr {

    /**
     * 整體思路是 左右分别開始累加求和 當左邊小時左邊下标右移，右邊小時右邊下标左移
     * 值到左右相等時，取中間部分在對其做一次如上的左右求和對比過程看能否找到中間的平衡點
     * 記得要效驗 平衡點的和與之前的和是否相等
     * @return
     */

    private static Boolean resolve(int[] a) {
        if (a == null || a.length < )
            return false;
        boolean result = false;
        int i = ;
        int j = a.length - ;
        int suml = a[i];
        int sumr = a[j];
        while (i < j) {
            if (suml < sumr) {
                i++;
                suml += a[i];
            } else if (suml > sumr) {
                j--;
                sumr += a[j];
            } else if (suml == sumr) {
                result = checkMiddle(i + , j - , suml, a);
                if (result) {
                    return result;
                } else {
                    i++;
                    suml += a[i];
                }
            }
        }
        return result;
    }

    private static boolean checkMiddle(int start, int end, int sum, int[] a) {

        int i = start + ;
        int j = end - ;
        int suml = a[i];
        int sumr = a[j];
        while (j > i) {
            if (suml < sumr) {
                i++;
                suml += a[i];
            } else if (suml > sumr) {
                j--;
                sumr += a[j];
            } else if (suml == sumr) {
                if (j - i ==  && suml == sum) {
                    return true;
                } else {
                    return false;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] a = { , , , , , , ,  }; // true
        int[] a1 = { , , , , , , ,  }; // false
        int[] a2 = { , , , , , , , ,  }; // true
        System.out.println(resolve(a2));
    }

}