java算法题-将数组分成和相等的三个部分

本文主要是介绍java算法题-将数组分成和相等的三个部分，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

在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

提示：

1. 3 <= A.length <= 50000
2. -10^4 <= A[i] <= 10^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
欢迎交流，共同进步。

这篇关于java算法题-将数组分成和相等的三个部分的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！