1013. Partition Array Into Three Parts With Equal Sum(Leetcode每日一题-2020.03.11)

本文主要是介绍1013. Partition Array Into Three Parts With Equal Sum(Leetcode每日一题-2020.03.11)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem

Given an array A of integers, return true if and only if we can partition the array into three non-empty parts with equal sums.

Formally, we can partition the array if we can find indexes i+1 < j with (A[0] + A[1] + … + A[i] == A[i+1] + A[i+2] + … + A[j-1] == A[j] + A[j-1] + … + A[A.length - 1])

Example1

Input: A = [0,2,1,-6,6,-7,9,1,2,0,1]
Output: true
Explanation: 0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1

Example2

Input: A = [0,2,1,-6,6,7,9,-1,2,0,1]
Output: false

Example3

Input: A = [3,3,6,5,-2,2,5,1,-9,4]
Output: true
Explanation: 3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4

Solution

在数组上切两刀，分成的三段至少要有一个元素，且三段元素之和相等。

那么，整个数组元素之和sum应该能被3整除，且sum/3就是每一段的和。

class Solution {
public:bool canThreePartsEqualSum(vector<int>& A) {if(A.size() < 3)return false;int sum = accumulate(A.begin(),A.end(),0);if(sum % 3 != 0)return false;int curSum = 0;int cnt = 0;for(int i = 0;i<A.size();++i){curSum += A[i];if(curSum == sum /3){++cnt;if(cnt == 3){return true;}curSum = 0;}}return false;}};

这篇关于1013. Partition Array Into Three Parts With Equal Sum(Leetcode每日一题-2020.03.11)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---