Straightforward solution...not fast but easy to understand


  • 0
    class Solution {
    public:
        bool splitArray(vector<int>& nums) {
            int size = nums.size();
            if(size<7)
                return false;
            for(int i=3;i<size-3;++i){
                //Divide the array into two parts
                unordered_set<int> left = split(nums,0,i);//If left part have equal sum
                unordered_set<int> right = split(nums,i+1,size);//If right part have equal sum
                for(auto sum:left){
                    if(right.find(sum)!=right.end())//Check the left part sum whether in right part
                        return true;
                }
            }
            return false;
        }
        
        unordered_set<int> split(const vector<int> &nums,int left,int right){
            vector<int> sum(right,0);
            unordered_set<int> res;
            int count = 0;
            for(int i=left;i<right;++i){// accmulate sum from left to i
                count += nums[i];
                sum[i-left] = count;
            }
            
            for(int i=left+1;i<right-1;++i){//check the subarry whether have split point
                if(sum[i-1-left]==sum[right-1-left]-sum[i-left])
                    res.insert(sum[i-1-left]);
            }
            return res;
            
        }
    };
    

    If i was wrong please let me know :)


Log in to reply
 

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