548. Split Array with Equal Sum

O(n²) time O(n) space
常规遍历ijk需要O(n³)，为了降低复杂度，先枚举j，然后分别枚举i和k，在枚举i的时候，如果遇到s[0:i-1] == s[i+1:j-1]则cache起来，这样在枚举k的时候，直接可以判断cache里是否存在s[j+1:k-1] == s[k+1:n-1]

class Solution {
public:
    bool splitArray(vector<int>& nums) {
        int n = nums.size();
        if (n < 7) return false;
        vector<int> presum(1);
        for (int x : nums) {
            presum.push_back(presum.back() + x);
        }
        for (int j = 3; j <= n - 4; ++j) {
            unordered_set<int> t;
            for (int i = 1; i <= j - 2; ++i) {
                if (presum[i] == presum[j] - presum[i + 1]) {
                    t.insert(presum[i]);
                }
            }
            for (int k = j + 2; k <= n - 2; ++k) {
                if (presum[k] - presum[j + 1] == presum[n] - presum[k + 1] && t.count(presum[k] - presum[j + 1])) return true;
            }
        }
        return false;
    }
};

O(n²) time O(n²) space

class Solution {
public:
    bool splitArray(vector<int>& nums) {
        int n = nums.size();
        if (n < 7) return false;
        int s = accumulate(begin(nums), end(nums), 0), s0 = nums[0];
        vector<unordered_set<int>> m(n);
        int t = nums[0] + nums[1] + nums[2];
        for (int j = 3; j <= n - 4; ++j) {
            t += nums[j];
            int s2 = nums[j + 1];
            for (int k = j + 2; k <= n - 2; ++k) {
                int s3 = s - (t + s2 + nums[k]);
                if (s2 == s3) {
                    m[j].insert(s2);
                }
                s2 += nums[k];
            }
        }
        for (int i = 1; i <= n - 6; ++i) {
            int s1 = nums[i + 1];
            for (int j = i + 2; j <= n - 4; ++j) {
                if (s0 == s1 && m[j].count(s1)) return true;
                s1 += nums[j];
            }
            s0 += nums[i];
        }
        return false;
    }
};