LeetCode 1013. Partition Array Into Three Parts With Equal Sum

原题链接在这里：https://leetcode.com/problems/partition-array-into-three-parts-with-equal-sum/description/

题目：

Given an array of integers arr, return true 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 (arr[0] + arr[1] + ... + arr[i] == arr[i + 1] + arr[i + 2] + ... + arr[j - 1] == arr[j] + arr[j + 1] + ... + arr[arr.length - 1])

Example 1:

Input: arr = [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

Example 2:

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

Example 3:

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

Constraints:

• 3 <= arr.length <= 5 * 104
• -104 <= arr[i] <= 104

题解：

Find out if the array could be dividied into three subarrays with equal sum.

Get the sum of array, if it is not divisable by 3, then it can't be divided into 3 equal sum subarrays, return false.

Otherwise, whenever we hit sum / 3, we accumlate the count by plus one.

Eventually check if the count is >= 3. 

Reason why count >= 3, there could be 0, 0, 0, 0. It could still be divided into 3 groups, with one group having 2 0s.

At the end, it should not check if curSum == 0 since there could be case that [-1, -1, -1, -1, -1, 2], when count = 5 and curSum = 2.

Time Complexity: O(n). Space: O(1).

AC Java:

 1 class Solution {
 2     public boolean canThreePartsEqualSum(int[] arr) {
 3         if(arr == null || arr.length == 0){
 4             return false;
 5         }
 6 
 7         int sum = 0;
 8         for(int num : arr){
 9             sum += num;
10         }
11 
12         if(sum % 3 != 0){
13             return false;
14         }
15 
16         int count = 0;
17         int target = sum / 3;
18         int curSum = 0;
19         for(int num : arr){
20             curSum += num;
21             if(curSum == target){
22                 count++;
23                 curSum = 0;
24             }
25         }
26 
27         return count >= 3;
28     }
29 }