力扣1712.将数组分成三个子数组的方案数

力扣1712.将数组分成三个子数组的方案数

• 确定左边界的值 然后二分求右边界的范围

  • 

  • 右边界处的前缀和满足 2*s[i] <= s[r] <= (s[n] + s[i]) / 2

•   int s[100010];
    const int N = 1e9+7;
    class Solution {
    public:
        int waysToSplit(vector<int>& nums) {
            int n = nums.size();
            int res=0;
            for(int i=1;i<=n;i++)
                s[i] = s[i-1] + nums[i-1];
            for(int i=1;i<=n;i++)
            {
                //返回的是指针 不能用int
                //找到第一个>=2*s[i]的数
                auto l = lower_bound(s+i+1,s+n,2*s[i]);
                //找到第一个>(s[n] + s[i])/2的数
                auto r = upper_bound(s+i+1,s+n,(s[n] + s[i])/2);
                int sum = r - l;
                if(sum > 0) res = (res + sum) %N;
            }
            return res;
        }
    };