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%的用户

执行用时分布图表

java算法题-将数组分成和相等的三个部分
执行消耗内存分布图表

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

大家有更好的解题思路吗?欢迎在评论区作答哈~
有问题也可发送至:1966353889@qq.com
欢迎交流,共同进步。

上一篇:牛客多校2021(四)J.Average(二分、前缀和)


下一篇:练习3-3 统计学生平均成绩与及格人数 (15分)