package alibaba;
import java.util.HashMap;
import java.util.Map;
/**
* Created by liuyang on 17/3/3.
* é˜¿é‡Œå®žä¹ ç¬”è¯•é¢˜æ•°ç»„å››ç‰åˆ†,最åŽé€šè¿‡çŽ‡80%
*/
public class ArrayDivide{
static boolean resolve(int[] A) {
if (A == null || A.length < 3) {
return false;
}
int len = A.length;
int[] sum = new int[len]; //当å‰ä½ç½®ç´¯åŠ å’Œ
Map map = new HashMap<>();//ç´¯åŠ å’Œå¯¹åº”çš„ä¸‹æ ‡
for (int i = 0; i < len; i++) {
sum[i] = i != 0 ? sum[i - 1] + A[i] : A[i];
map.put(sum[i], i);
}
int left = 0;
int right = len - 1;
while (left < right) {
if (sum[left] < sum[len - 1] - sum[right - 1]) {
left++;
} else if (sum[left] > sum[len - 1] - sum[right - 1]) {
right--;
} else {
int target = sum[left] + A[left + 1] + sum[left];
if (map.containsKey(target)) {
int mid = map.get(target);
if (mid < right && sum[right - 2] - sum[mid + 1] == sum[left]) {
return true;
}
}
left++;
}
}
return false;
}
public static void main(String[] args) {
int[] A = {2, 5, 1, 2, 1, 4, 1, 7, 3, 7};
System.out.println(resolve(A));
}
}