What is the core approach to solve the 'Ways to Split Array Into Three Subarrays' problem?

The core approach is to use binary search over the possible sum values combined with prefix sums to efficiently find valid splits.

How do I optimize the solution for large arrays in the 'Ways to Split Array Into Three Subarrays' problem?

By using binary search over the valid sum space and leveraging prefix sums for constant-time subarray sum calculations, the solution can scale efficiently.

What is the role of the prefix sum in this problem?

The prefix sum allows for quick calculation of subarray sums, which is crucial for efficiently checking if a potential split meets the sum condition.

What are common pitfalls when solving the 'Ways to Split Array Into Three Subarrays' problem?

Common pitfalls include neglecting to use prefix sums, not optimizing the binary search step, and overlooking edge cases where no valid split exists.

Can this problem be generalized to more than three subarrays?

Yes, the problem can be generalized to more subarrays, though this introduces additional complexity in both the binary search and validation steps.

#1712

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

将数组分成三个子数组的方案数

我们称一个分割整数数组的方案是好的，当它满足：数组被分成三个非空连续子数组，从左至右分别命名为 left ， mid ， right 。 left 中元素和小于等于 mid 中元素和， mid 中元素和小于等于 right 中元素和。给你一个非负整数数组 nums ，请你返回好的 …

数组双指针二分查找前缀和

题目描述

我们称一个分割整数数组的方案是好的，当它满足：

数组被分成三个非空连续子数组，从左至右分别命名为 left ， mid ， right 。
left 中元素和小于等于 mid 中元素和，mid 中元素和小于等于 right 中元素和。

给你一个非负整数数组 nums ，请你返回好的分割 nums 方案数目。由于答案可能会很大，请你将结果对 10⁹+ 7 取余后返回。

示例 1：

输入：nums = [1,1,1]
输出：1
解释：唯一一种好的分割方案是将 nums 分成 [1] [1] [1] 。

示例 2：

输入：nums = [1,2,2,2,5,0]
输出：3
解释：nums 总共有 3 种好的分割方案：
[1] [2] [2,2,5,0]
[1] [2,2] [2,5,0]
[1,2] [2,2] [5,0]

示例 3：

输入：nums = [3,2,1]
输出：0
解释：没有好的分割方案。

提示：

3 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁴

lightbulb

解题思路

方法一：前缀和 + 二分查找

我们先预处理出数组 $nums$ 的前缀和数组 $s$ ，其中 $s[i]$ 表述数组 $nums$ 前 $i+1$ 个元素之和。

由于数组 $nums$ 的元素都是非负整数，因此前缀和数组 $s$ 是一个单调递增数组。

我们在 $[0,..n-2)$ 的范围内枚举 left 子数组所能到达的下标 $i$ ，然后利用前缀和数组单调递增的特性，通过二分查找的方式找到 mid 子数组分割的合理范围，记为 $[j, k)$ ，累加方案数 $k-j$ 。

二分细节上，子数组分割必须满足 $s[j] \geq s[i]$ ，并且 $s[n - 1] - s[k] \geq s[k] - s[i]$ 。即 $s[j] \geq s[i]$ ，且 $s[k] \leq \frac{s[n - 1] + s[i]}{2}$ 。

最后，将方案数对 $10^9+7$ 取模后返回即可。

时间复杂度 $O(n \times \log n)$ 。其中 $n$ 为数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def waysToSplit(self, nums: List[int]) -> int:
        mod = 10**9 + 7
        s = list(accumulate(nums))
        ans, n = 0, len(nums)
        for i in range(n - 2):
            j = bisect_left(s, s[i] << 1, i + 1, n - 1)
            k = bisect_right(s, (s[-1] + s[i]) >> 1, j, n - 1)
            ans += k - j
        return ans % mod

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates the ability to handle large inputs efficiently using binary search and prefix sums.
question_mark
The candidate identifies and uses a two-pointer technique to validate subarray splits in an optimized way.
question_mark
The candidate understands the trade-off between different approaches and chooses the most efficient one.

warning

常见陷阱

外企场景

error
Not utilizing prefix sums, leading to inefficient subarray sum checks.
error
Failing to optimize the binary search step, resulting in suboptimal performance for larger inputs.
error
Overlooking edge cases where no valid split exists, returning incorrect results for such inputs.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Different variations of the problem could involve finding splits based on conditions other than sum equality, such as minimum or maximum values.
arrow_right_alt
This problem could be extended to more than three subarrays, which would introduce more complexity into the binary search and validation steps.
arrow_right_alt
In some cases, the constraints might change, requiring a solution that works for even larger arrays or different input value ranges.

help

常见问题

外企场景

继续练习

#1508 子数组和排序后的区间和 #2234 花园的最大总美丽值 #1658 将 x 减到 0 的最小操作数