在leetcode(https://leetcode-cn.com/)上看到一道有趣的算法题:
给你一个整数数组 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
提示:
这样的题你会怎么用java实现呢?
分享一下我的解题思路:
public Boolean canThreePartsEqualSum(int[] arr) { int length=arr.length; if(length==3&&!(arr[0]==arr[1]&&arr[1]==arr[2])){ return false; } int total=getTotal(arr); if(total%3>0){ return false; } /*计算平均数(满足条件的数组叠加和)*/ int average=total/3; int left=1; int right=length-2; /*左边数组元素叠加的值(预叠加一次)*/ int leftSum=arr[0]; /*右边数组元素叠加的值(预叠加一次)*/ int rightSum=arr[length-1]; while(left<right){ if(leftSum!=average){ leftSum+=arr[left]; left++; } if(rightSum!=average){ rightSum+=arr[right]; right--; } if((leftSum==average&&rightSum==average)){ break; } } if(left>right){ return false; } if(leftSum==average&&rightSum==average){ /*计算剩余中间的数组元素的叠加和*/ return getSum(left,right,arr)==average; } return false; } /**计算arr数组元素的叠加和*/ private int getTotal(int[] arr){ int left=0; int right=arr.length-1; int sum=0; while(left<=right){ if(left==right){ sum+=arr[left]; } else{ sum+=(arr[left]+arr[right]); } left++; right--; } return sum; } /**计算arr数组中元素position范围在left到right(包括right)的叠加和*/ private int getSum(int left,int right,int[] arr){ System.out.println("left="+left+",right="+right); int result=0; for (int i=left;i<right+1;i++){ result+=arr[i]; } return result; }
结果:
输入:[0,2,1,-6,6,-7,9,1,2,0,1] 输出:true
leetcode上对该答案的分析如下:
72 / 72 个通过测试用例
状态:通过
执行用时: 12 ms 在所有 Java 提交中击败了7.43%的用户
内存消耗: 46.6 MB, 在所有 Java 提交中击败了5.32%的用户
执行用时分布图表
执行消耗内存分布图表
大家有更好的解题思路吗?欢迎在评论区作答哈~
有问题也可发送至:1966353889@qq.com
欢迎交流,共同进步。