1013. Partition Array Into Three Parts With Equal Sum

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

这题需要找到两个索引，使得一个数组能够分为三个非空的子数组，并且它们的和相同。

首先我们可以确定，它们的和肯定是确定的，是总和处以3，那么我们可以提前的去掉那些不符合被3整除的场景。

我们只要从前和从后找到符合的索引即可。

class PartitionArrayIntoThreePartsWithEqualSum : public Solution {
  public:
    void Exec() {
        cout << "Case 1: "
             << canThreePartsEqualSum(
                    vector<int>{0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1})
             << std::endl
             << "Case 2: "
             << canThreePartsEqualSum(
                    vector<int>{0,2,1,-6,6,7,9,-1,2,0,1})
             << std::endl
             << "Case 3: "
             << canThreePartsEqualSum(
                    vector<int>{3,3,6,5,-2,2,5,1,-9,4})
             << std::endl
             << "Case 4: "
             << canThreePartsEqualSum(
                    vector<int>{1, 2 ,1})
             << std::endl
             << "Case 5: "
             << canThreePartsEqualSum(
                    vector<int>{1, 1, 1})
             << std::endl
             << "Case 6: "
             << canThreePartsEqualSum(
                    vector<int>{1, -1, 1, -1})
             << std::endl;
    }

    bool canThreePartsEqualSum(const vector<int> &arr) {
        int sum = 0;
        for (auto v : arr) {
            sum += v;
        }
        if (sum % 3 != 0) {
            return false;
        }

        int left = -1, right = arr.size();
        int lsum = 0, rsum = 0;
        for (int i = 0; i < arr.size(); i++) {
            lsum += arr[i];

            if (lsum == sum / 3) {
                left = i;
                break;
            }
        }
        for (int i = arr.size() - 1; i >= 0; i--) {
            rsum += arr[i];

            if (rsum == sum / 3) {
                right = i;
                break;
            }
            if (i - left < 2) {
                return false;
            }
        }
        if (left < 0 || right >= arr.size() || right - left < 2) {
            return false;
        }

        return true;
    }
};