How to Partition an Array Into Three Parts With Equal Sum?
- 时间:2020-10-06 11:32:45
- 分类:网络文摘
- 阅读:76 次
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])
Example 1:
Input: [0,2,1,-6,6,-7,9,1,2,0,1]
Output: true
Explanation: 0 + 2 + 1 = -6 + 6 – 7 + 9 + 1 = 2 + 0 + 1Example 2:
Input: [0,2,1,-6,6,7,9,-1,2,0,1]
Output: falseExample 3:
Input: [3,3,6,5,-2,2,5,1,-9,4]
Output: true
Explanation: 3 + 3 = 6 = 5 – 2 + 2 + 5 + 1 – 9 + 4Note:
3 <= A.length <= 50000
-10000 <= A[i] <= 10000
Array Paritition Algorithm via Brute-force Algorithm
We can have two index pointers i, and j, which runs at O(N^2) time complexity. We also keep updated partial sum from 0 to i and i to j respectively, then we need to check if these two paritial sums are equal and also equal to the remainder.
This brute force algorithm is slow, which gives a time limit exceeded error if the input list is huge.
Compute the Average
We can do a O(N) to compute the sum first. Then, we know the one third of the sum. When we go through the array, we accumulate the sum, if it is equal to the average, we increment the counter and reset the sum.
At the end of the array O(N), if the counter is three and the current sum is zero, we know that the list can be divided into perfectly 3 equal parts.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | class Solution { public: bool canThreePartsEqualSum(vector<int>& A) { int avg = std::accumulate(begin(A), end(A), 0, [](auto &a, auto &b) {return a + b; }) / 3; int cur = 0; int count = 0; for (int i = 0; i < A.size(); ++ i) { cur += A[i]; if (cur == avg) { count ++; cur = 0; } } return count == 3 && cur == 0; } }; |
class Solution { public: bool canThreePartsEqualSum(vector<int>& A) { int avg = std::accumulate(begin(A), end(A), 0, [](auto &a, auto &b) {return a + b; }) / 3; int cur = 0; int count = 0; for (int i = 0; i < A.size(); ++ i) { cur += A[i]; if (cur == avg) { count ++; cur = 0; } } return count == 3 && cur == 0; } };
To compute the sum, we can use the std::accumulate instead of the tradition for-loop.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:总会有一个人是无可替代的。 不要畏惧痛苦作文900字 都是马虎惹的祸作文100字 圣诞节的作文600字 春天的雨小学生作文 三下乡之七月十四号 打台球作文250字 龟兔赛跑数学问题 相遇后再追及的数学问题 小花在此次比赛中答错了几道题
- 评论列表
-
- 添加评论