[LeetCode]: 548. Split Array with Equal Sum

https://leetcode.com/contest/leetcode-weekly-contest-26/problems/split-array-with-equal-sum/

Solution:
This question is not very difficult, but the brute force loop cannot pass the OJ. So we need to find some way to use the intermediate information which means the one we have already calculated. Since we have already calculated it, there's no need to calculate it again. Instead, we can use the result from the previous calculation directly. That is exactly what is called memorization. DP is the one of the most common ways of memorization. The key point is: can the question be divided into sub-questions? If the answer is yes, then we can apply memorization.

For this question, for example, suppose we have already calculated that sum[i], meaning sum from 0 to i, is NOT the place where we can split the array with equal sum as required by the question, then in the latter processing, once we meet with the same value (sum[ii] == sum[i]), we can directly make a negative judge. (if sum[ii] == sum[i], which means the sum from i+1 to ii-1 is 0, so if the final result for sum[ii] is yes, then sum[i] should be yes too. But it is not, so sum[ii] must be no.) A hash map is enough to do memorization. See the code below:

Code:

class Solution {
public:
    bool splitArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> sum;
        for(int i=0; i<n; ++i) i==0?sum.push_back(nums[i]):sum.push_back(nums[i] + sum[i-1]);
        unordered_map<int, bool> m;
        for(int i=0; i<n-1; ++i){
            if(m.find(sum[i]) == m.end()){
                for(int j=i+2; j<n-1; ++j){
                    if(sum[j]-sum[i+1]==sum[i]){
                        for(int k=j+2; k<n-2; ++k){
                            if(sum[k]-sum[j+1]==sum[i]&&sum[n-1]-sum[k+1]==sum[i]) return true;
                        }
                    }
                }
                m[sum[i]] = false;
            }
        }
        return false;
    }
};