package shuzu;
import java.util.HashMap;
/*
1013. 将数组分成和相等的三个部分
给你一个整数数组 A，只有可以将其划分为三个和相等的非空部分时才返回 true，否则返回 false。
形式上，如果可以找出索引 i+1 < j 且满足 A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1] 就可以将数组三等分。
示例 1：
输入：[0,2,1,-6,6,-7,9,1,2,0,1]
输出：true
解释：0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1
示例 2：
输入：[0,2,1,-6,6,7,9,-1,2,0,1]
输出：false
示例 3：
输入：[3,3,6,5,-2,2,5,1,-9,4]
输出：true
解释：3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4
提示：
3 <= A.length <= 50000
-10^4 <= A[i] <= 10^4
解题思路：
首先得到整个数组的和
然后遍历和/3
是不是可以用hashmap储存结果然后以空间换时间呢？//前缀和------未完全通过 52/55
思路2：
思路1的基础上双指针
左右齐头并进，为sum/3后，中间的一定为sum/3
若两指针碰见，则False
当 left + 1 < right 的约束下，可以找到数组两头的和都是 sum/3,那么中间剩下的元素和就一定也是sum/3
（left + 1 < right的约束就是要中间有剩下的元素，使用left < right的约束，数组可能可以恰好被划分成两部分，中间没有元素）
*/
public class p1013 {
//未完全通过，52/55
/*public static boolean canThreePartsEqualSum(int[] A) {
int sum_i=0;
HashMap<Integer,Integer>map=new HashMap<>();//key为前缀和，i为index
map.put(0,-1);
for(int i=0;i<A.length;i++){
sum_i+=A[i];
map.put(sum_i,i);
}
System.out.println("和"+sum_i);
if(sum_i%3!=0||!map.containsKey(2*sum_i/3)||!map.containsKey(sum_i/3))return false;
if(map.containsKey(2*sum_i/3)&&map.containsKey(sum_i/3)){
if(map.get(sum_i/3)>map.get(2*sum_i/3)){
return false;
}
}
return true;
}*/
//双指针
public static boolean canThreePartsEqualSum(int[] A){
int left=0,right=A.length-1,sum=0;
for(int i=0;i<A.length;i++)sum+=A[i];
if(sum%3!=0)return false;
int sumleft=A[left],sumright=A[right];
while (left<right-1){
if(sumleft==sum/3&&sumright==sum/3)return true;
if(sumleft!=sum/3){
left++;
sumleft+=A[left];
}
if(sumright!=sum/3){
right--;
sumright+=A[right];
}
}
return false;
}
public static void main(String[] args) {
//1,-1,1,-1
int a[]={};
System.out.println(canThreePartsEqualSum(a));
}
}
运行结果：
