C++ easy solution with explaination

  • 0

    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 {
        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];
            for(int i = 1; i < size; i++){   //build sum array and hash table
                firstIter[i] = firstIter[i-1]+nums[i];
            int sum = 0;
            for(int i = size-1; i >= 6; i--){  //traverse from end, find two equal outside blocks
                    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.