C++ Solution, two pointer O(n^2), 19ms


  • 0
    T
    class Solution {
    public:
        bool splitArray(vector<int>& nums) {
            if(nums.size() < 7) return false;
            int total = 0;
            for(auto& num:nums)
                total+=num;
            int leftSum = nums[0];
            for(int i = 1; i < nums.size();i++){
                int rightSum = nums[nums.size()-1];
                for(int j = nums.size()-2; j-i>2; j--){
                    if(leftSum == rightSum && splitArray(nums, total-leftSum*2-nums[i]-nums[j], leftSum, i+1, j-1)){
                        return true; 
                    }
                    rightSum+=nums[j];
                }
                leftSum+=nums[i];
            }
            return false;
        }
        
        bool splitArray(vector<int>&nums, int rest, int target, int b, int e){
            int sum = nums[b];
            rest-=nums[b];
            for(int i = b+1; i< e; i++){
                rest-=nums[i];
                if(sum== target && rest==target)
                    return true;
                sum+=nums[i];
            }
            return false;
        }
    };
    

Log in to reply
 

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