對(duì)于一個(gè)長(zhǎng)度為N的整型數(shù)組A靡羡， 數(shù)組里所有的數(shù)都是正整數(shù)贱鄙，對(duì)于兩個(gè)滿足0 <= X <= Y < N的整數(shù)翁都，A[X], A[X+1] … A[Y]構(gòu)成A的一個(gè)切片，記作(X, Y).
用三個(gè)下標(biāo) m1, m2, m3（下標(biāo)滿足條件0 < m1, m1 + 1 < m2, m2 +1 < m3 < N – 1）可以把這個(gè)整型數(shù)組分成(0, m1-1), (m1+1, m2-1), (m2+1, m3-1), (m3+1, N-1) 四個(gè)切片寒砖。
如果這四個(gè)切片的整數(shù)求和相等赐劣，稱作“四等分”。編寫(xiě)一個(gè)函數(shù)哩都，求一個(gè)給定的整型數(shù)組是否可以四等分魁兼，如果可以，返回一個(gè)布爾類型的true漠嵌，如果不可以返回一個(gè)布爾類型的false咐汞。
限制條件：數(shù)組A最多有1,000,000項(xiàng)，數(shù)組中的整數(shù)取值范圍介于-1,000,000到1,000,000之間献雅。
要求：函數(shù)的計(jì)算復(fù)雜度為O(N)碉考，使用的額外存儲(chǔ)空間（除了輸入的數(shù)組之外）最多為O(N)塌计。例子：
對(duì)于數(shù)組A=[2, 5, 1, 1, 1, 1, 4, 1, 7, 3, 7] 存在下標(biāo) 2, 7, 9使得數(shù)組分成四個(gè)分片[2, 5], [1, 1, 1, 4], [7], [7]挺身，這三個(gè)分片內(nèi)整數(shù)之和相等，所以對(duì)于這個(gè)數(shù)組锌仅，函數(shù)應(yīng)該返回true章钾。
對(duì)于數(shù)組 A=[10, 2, 11, 13, 1, 1, 1, 1, 1]，找不到能把數(shù)組四等分的下標(biāo)热芹，所以函數(shù)應(yīng)該返回false贱傀。
今年參加了阿里的實(shí)習(xí)生春招，在進(jìn)行編程測(cè)驗(yàn)之前已經(jīng)了解到部分同學(xué)遇到的是這道題伊脓，所以事先做了準(zhǔn)備府寒，然而輪到我時(shí)已經(jīng)換題了，可能是不同崗位題目不一樣吧报腔。
這道題描述的啰哩啰嗦株搔，實(shí)際上就是給一個(gè)全是正數(shù)的數(shù)組，問(wèn)是否能將該數(shù)組分割成四部分纯蛾，每一部分累加和相等纤房，分割點(diǎn)不算
要解決這題首先要明確數(shù)組四等分的結(jié)構(gòu)，即3個(gè)分割點(diǎn)翻诉，4個(gè)切片炮姨，有了這個(gè)概念，在草紙上畫(huà)畫(huà)碰煌，問(wèn)題很容易就解決了舒岸。
首先我們遍歷一遍數(shù)組構(gòu)造一個(gè)HashMap存儲(chǔ) ( arr[i]左邊所有元素的和 , i ) ，然后大多數(shù)人選擇讓分割點(diǎn)m1芦圾、m3從兩端像中間移動(dòng)的同時(shí)累加兩個(gè)切片內(nèi)元素（誰(shuí)小誰(shuí)移動(dòng)）吁津，當(dāng)兩個(gè)切片相等時(shí)根據(jù)四等分結(jié)構(gòu)看能否找到滿足條件的分割點(diǎn)m2。
這里我選擇僅將分割點(diǎn)m1由左向右移動(dòng)，如果數(shù)組可以四等分碍脏，依據(jù)3個(gè)分割點(diǎn)梭依，4個(gè)切片這樣一個(gè)基本結(jié)構(gòu)，一旦分割點(diǎn)m1確定了典尾，m2役拴、m3也就相應(yīng)確定了，如果最后找不到符合基本結(jié)構(gòu)的m2钾埂、m3河闰，則可以斷定數(shù)組不可以四等分，時(shí)間復(fù)雜度O(N)褥紫，代碼如下：
public static boolean canSplits(int[] arr) {
if (arr == null || arr.length < 7) { // 元素個(gè)數(shù)小于7姜性，無(wú)法構(gòu)成3個(gè)分割點(diǎn)、4個(gè)切片的基本結(jié)構(gòu)
return false;
}
HashMap<Long, Integer> leftSumToIndex = new HashMap<>();
Long sum = (long) arr[0];
for (int i = 1; i < arr.length; i++) {
leftSumToIndex.put(sum, i); // 把(arr[i]左邊所有元素的和, i)存入HashMap
sum += arr[i];
}
Long part = (long) arr[0]; // part為切片內(nèi)元素的和
for (int m1 = 1; m1 < arr.length - 5; m1++) { // 遍歷分割點(diǎn)m1
Long m2LeftSum = part + arr[m1] + part; // 分割點(diǎn)m2左邊所有元素的和
if (leftSumToIndex.containsKey(m2LeftSum)) {
int m2 = leftSumToIndex.get(m2LeftSum);
Long m3LeftSum = m2LeftSum + arr[m2] + part; // 分割點(diǎn)m3左邊所有元素的和
if (leftSumToIndex.containsKey(m3LeftSum)) {
int m3 = leftSumToIndex.get(m3LeftSum);
if (m3LeftSum + arr[m3] + part == sum) {
return true;
}
}
}
part += arr[m1];
}
return false;
}
對(duì)于像Two Sum髓考、Longest Substring Without Repeating Characters以及本題這種涉及數(shù)組下標(biāo)的一系列問(wèn)題部念，優(yōu)先考慮事先構(gòu)造一個(gè)HashMap看是否對(duì)后續(xù)的求解有幫助。在HashMap中氨菇，每次查詢操作的時(shí)間復(fù)雜度均為O(1)儡炼，所以它一直是編寫(xiě)高效算法的利器。
