【題解】LeetCode 1712. Ways to Split Array Into Three Subarrays

【題目敘述】https://leetcode.com/problems/ways-to-split-array-into-three-subarrays/

class Solution {
public:
    int waysToSplit(vector<int>& v) {
        int pre[100005];
        pre[0] = 0;
        for (int i = 0; i < v.size(); i++){
            pre[i+1] = pre[i]+v[i]; 
        }
        int b = 3, c = 3;
        long long ans = 0;
        for (int a = 2; a < v.size(); a++){
            b = max(b, a+1);
            while (b <= v.size() && pre[b-1]-pre[a-1] < pre[a-1]) b++;
            if (b > v.size()) break;
            while (c <= v.size() && pre[v.size()]-pre[c-1] >= pre[c-1]-pre[a-1]) c++;
            c--;
            if (!(pre[v.size()]-pre[c-1] >= pre[c-1]-pre[a-1])) continue; 
            if (b <= c){
                ans += c-b+1;
            }
        }
        return ans % (int)(1e9+7);
    }
};
分享本文 Share with friends