548. Split Array with Equal Sum

Given an array with n integers, you need to find if there are triplets (i, j, k) which satisfies following conditions:

1. 0 < i, i + 1 < j, j + 1 < k < n - 1

2. Sum of subarrays (0, i - 1), (i + 1, j - 1), (j + 1, k - 1) and (k + 1, n - 1) should be equal.

where we define that subarray (L, R) represents a slice of the original array starting from the element indexed L to the element indexed R.

Example:

Input: [1,2,1,2,1,2,1]
Output: True
Explanation:
i = 1, j = 3, k = 5. 
sum(0, i - 1) = sum(0, 0) = 1
sum(i + 1, j - 1) = sum(2, 2) = 1
sum(j + 1, k - 1) = sum(4, 4) = 1
sum(k + 1, n - 1) = sum(6, 6) = 1

Note:

1. 1 <= n <= 2000.

2. Elements in the given array will be in range [-1,000,000, 1,000,000].

暴力解只是練習，無法通過OJ。

// Brute Force
bool splitArray(vector<int>& nums) { // time: O(n^3); space: O(n)
    int n = nums.size();
    vector<int> sums(n, 0);
    sums[0] = nums[0];
    for (int i = 1; i < n; ++i) {
        sums[i] = sums[i - 1] + nums[i];
    }
    for (int i = 1; i < n - 5; ++i) {
        int sum1 = sums[i - 1];
        for (int j = i + 2; j < n - 3; ++j) {
            int sum2 = sums[j - 1] - sums[i];
            if (sum2 != sum1) continue;
            for (int k = j + 2; k < n - 1; ++k) {
                int sum3 = sums[k - 1] - sums[j];
                int sum4 = sums[n - 1] - sums[k];
                if (sum2 == sum3 && sum3 == sum4) {
                    return true;
                }
            } 
        }
    }
    return false;
}

先找出middle cut的位置，接著找出left cut的位置，利用two sum的概念把可能的和存入unordered_set裡，等loop right cut的位置時，就可以幫助快速找到可能的和是否有在第一個quarter和第二個quarter出現過。

bool splitArray(vector<int>& nums) { // time: O(n^2); space: O(n)
    int n = nums.size();
    vector<int> sums(n, 0); // nums[i] = sums[i] - sums[i - 1]
    sums[0] = nums[0];
    for (int i = 1; i < n; ++i) {
        sums[i] = sums[i - 1] + nums[i];
    }
    unordered_set<int> st;
    // i: left cut, j: mid cut, k: right cut
    for (int j = 3; j < n - 3; ++j) {
        st.clear();
        for (int i = 1; i < j - 1; ++i) {
            if (sums[i - 1] == sums[j - 1] - sums[i]) {
                st.insert(sums[i - 1]);
            }
        }
        if (st.empty()) continue;
        for (int k = j + 2; k < n - 1; ++k) {
            if (sums[n - 1] - sums[k] == sums[k - 1] - sums[j] && st.count(sums[k - 1] - sums[j])) {
                return true;
            }
        }
    }
    return false;
}