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)); } }
运行结果: