C++ easy solution with explaination


  • 0
    B

    This question can be divided into two part:
    First, find two equal outer blocks
    Second, for each combination of outer block, find if two inner blocks have same sum value
    The code runs in 9ms

    class Solution {
    public:
        bool splitArray(vector<int>& nums) {
            int size = nums.size();
            if(size < 7) return false;
            vector<int> firstIter(size, 0);    //sum array
            unordered_map<int, vector<int>> table; //hash table for search
            firstIter[0] = nums[0];
            table[firstIter[0]].push_back(0);
           
            for(int i = 1; i < size; i++){   //build sum array and hash table
                firstIter[i] = firstIter[i-1]+nums[i];
                table[firstIter[i]].push_back(i);
            }
            int sum = 0;
            for(int i = size-1; i >= 6; i--){  //traverse from end, find two equal outside blocks
                sum+=nums[i];
                if(table.count(sum)){
                    if(innerFind(i-2, table[sum], firstIter)) return true;  //for every outside situation, find valid inside blocks
                }
            }
            return false;
        }
        bool innerFind(int end, const vector<int>& candi, const vector<int>& firstIter){
            int size = candi.size();
            for(int i = 0; i < size; i++){
                int start = candi[i]+1;
                for(int j = start + 1; j <= end-2; j++){
                    if(firstIter[j] - firstIter[start] == firstIter[end] - firstIter[j+1]) return true;
                }
            }
            return false;
            
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.