原题
给你一个整数数组 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
解法
思想
这道题的思想就是一个数组如果能分成三个和相等的部分，首先获取这个均分的值是多少，假设是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/
相关推荐
-
leetcode1071-字符串的最大公因子
原题 对于字符串 S 和 T，只有在 S = T + ... + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。 返回最长字符串 X，要求满足 X 能除尽 ...
-
leetcode169-多数元素
原题 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例1:...
-
leetcode700-二叉搜索树中的搜索
原题 给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。 例如， 给定二叉搜索树...
-
leetcode60-第k个排列
原题 给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。 按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下： "123" "132" "21...
-
用一个栈实现另一个栈的排序
原题（来源牛客网） 一个栈中元素的类型为整型，现在想将该栈从顶到底按从大到小的顺序排序，只许申请一个栈。除此之外，可以申请新的变量，但不能申请额外的数据结构。如何完成排序？ 解法 ...
-
leetcode887-鸡蛋掉落
原题 你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。 每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。 你知道存在楼层 F ，满足 0 &...
-
拉帮结派的数据结构-并查集
本文参考资源： 超超有爱爱-----并查集~~~chen_zan_yu的博客-CSDN博客 概述 并查集通常用作集合的合并。 并查集是一种树形结构，又叫“不相交集合”，保持了一组不...
-
leetcode297-二叉树的序列化与反序列化
原题 序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。...
-
leetcode706-设计哈希映射
原题 不使用任何内建的哈希表库设计一个哈希映射 具体地说，你的设计应该包含以下的功能 put(key, value)：向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在，更...
-
leetcode658-找到K个最接近的元素
原题 给定一个排序好的数组，两个整数 k 和 x，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。如果有两个数与 x 的差值一样，优先选择数值较...
