C++ O(nlogn) 8 liners prefix and binary search solution with brief explanation and comments
Idea:\n1. sum(subarray1)<=sum(nums)/3\n2. sum(subarray2)>=sum(subarray1) and sum(subarray2)<=(sum(nums)-sum(subarray1))/2\n->so that sum(subarray3)>=sum(subarra
Idea:\n1. sum(subarray1)<=sum(nums)/3\n2. sum(subarray2)>=sum(subarray1) and sum(subarray2)<=(sum(nums)-sum(subarray1))/2\n->so that sum(subarray3)>=sum(subarray2)>=sum(subarray1)\n3. use nums directly to save space\n```\nint waysToSplit(vector<int>& nums) \n{\n\tlong result=0,n=nums.size(),d=1000000007;\n\tfor(int i=1;i<n;i++) nums[i]+=nums[i-1]; //use nums for prefix sum to save space\n\n\tfor(int i=0;i<n;i++)\n\t{\n\t\tif(nums[i]>nums.back()/3) break; //so that sum(subarray1)<=sum(nums)/3\n\n\t\tvector<int>::iterator low=lower_bound(nums.begin()+i+1,nums.end()-1,2*nums[i]); //so sum(subarray2)>=sum(subarray1)\n\t\tvector<int>::iterator up=upper_bound(low,nums.end()-1,nums[i]+(nums.back()-nums[i])/2); //so that sum(subarray2)<=sum(subarray3)\n\t\tresult=(result+up-low)%d;\n\t}\n\treturn result;\n}\n```
[]