1. 代码段小站首页
  2. 算法

leetcode1013-将数组分成和相等的三个部分

彭晨涛 • • 算法 • 阅读 53

原题

给你一个整数数组 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

解法

思想

这道题的思想就是一个数组如果能分成三个和相等的部分，首先获取这个均分的值是多少，假设是x，然后从左往右第一个和为x的区间必须要算入，第二个和为x的区间也必须要算入，剩下的元素就必须是第三个区间，即和必须为x。

代码

class Solution {
    public boolean canThreePartsEqualSum(int[] A) {
        int sum = 0;
        for(int i:A) sum+=i;
        if(sum%3!=0) return false;
        int single = sum/3;
        int cur = 0;
        int count = 0;
        for(int i = 0;i<A.length;i++){
            cur+=A[i];
            if(cur==single && count!=2) {
                count+=1;
                if(count==2&&i==A.length-1) return false;
                cur = 0;
            }
        }
        return count==2 && cur==single;
    }
}

原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode1013-%e5%b0%86%e6%95%b0%e7%bb%84%e5%88%86%e6%88%90%e5%92%8c%e7%9b%b8%e7%ad%89%e7%9a%84%e4%b8%89%e4%b8%aa%e9%83%a8%e5%88%86/

赞 (0)
彭晨涛彭晨涛管理者
0 0
上一篇 2020年3月11日 01:08
下一篇 2020年3月11日 12:24

相关推荐

发表回复

登录后才能评论