C++ EZ understanding 23ms-29ms clean math solution and something else...


  • 2

    Basicly we know:

    1. Need to find three point: x, y, z
    2. Total = 4*subArray + nums[x] + nums[y] + nums[z]

    then... I think the code will show you the idea...

    class Solution {
    public:
        bool splitArray(vector<int>& nums) {
            int i=0, j=nums.size()-2;
            int s=0; vector<int> sum;
            for(auto x: nums)
            {
                s+=x;
                sum.push_back(s);
            }
            int total = sum.back();
            for(j=nums.size()-2; j>i; j--)
            {
                for(i=0; i<j-1; i++)
                {
                    if(sum[i]==total-sum[j]) //found i+1 = x, j = z
                    {
                        int y = total - 4*sum[i] - nums[i+1] - nums[j]; 
                        for(int k = i+1+1; k < j-1; k++)
                            if(nums[k] == y) return true;
                    }
                }
                i=0;
            }
            return false;
        }
    };
    

    This one I thought will be faster but actually slower(29ms-45ms)... forget this one

    class Solution {
    public:
        bool splitArray(vector<int>& nums) {
            int i=0, j=nums.size()-2;
            int s=0; vector<int> sum;
            unordered_map<int, vector<int>> map;
            for(int x=0; x<nums.size(); x++)
            {
                s+=nums[x];
                map[nums[x]].push_back(x);
                sum.push_back(s);
            }
            int total = sum.back();
            for(j=nums.size()-2; j>i; j--)
            {
                for(i=0; i<j-1; i++)
                {
                    if(sum[i]==total-sum[j]) 
                    {
                        int y = total - 4*sum[i] - nums[i+1] - nums[j]; 
                        if(map.find(y)!=map.end())
                        {
                            for(int x=0; x<map[y].size(); x++)
                            {
                                vector<int> bs = map[y];
                                int step = lower_bound(bs.begin(), bs.end(), i+2) - bs.begin();
                                if(step < j-1) return true;
                            }
                        }
                    }
                }
                i=0;
            }
            return false;
        }
    };
    

Log in to reply
 

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