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

思路

二分法 + 哨兵

代码

var waysToSplit = function(nums) {
  const sumArr = [0], len = nums.length;
  for(let i = 1; i <= len; i ++) {
    sumArr[i] = nums[i - 1] + sumArr[i - 1]
  }
  let count = 0, mod = 10**9+7;
  for(let i = 1, l = 2, r = 2; i <= len - 1; i ++) {
    l = Math.max(l, i + 1), r = Math.max(r, i + 1)
    while(r <= len - 1 && sumArr[len] - sumArr[r] >= sumArr[r] - sumArr[i]) {
      r ++
    }
    while(l <= len - 1 && sumArr[l] - sumArr[i] < sumArr[i]) {
      l ++
    }
    if (l <= r) {
      count += r - l;
    }
  }
  return count % mod
};

复杂度分析

时间复杂度 $O(NlogN)$

空间复杂度 $O(N)$