103. Three Equal Slices
A farmer harvests a row of fields, and nums lists the crop weight in each field in order; a weight may be zero or negative after spoilage deductions. The farmer wants to split the row into three consecutive, non-empty sections so that all three sections have exactly the same total weight.
A split is described by the two positions where the row is cut. Return the number of different ways to cut nums into three non-empty contiguous slices with equal sums. If the total cannot be shared equally or no such cut exists, return 0. The result can be large, so it is returned as a 64-bit integer.
Example 1
- Input:
- nums = [1,2,0,3,0,3]
- Output:
- 4
- Explanation:
Each slice must sum to 3; cutting after index 1 or 2 and then after index 3 or 4 all work, so the answer is 4.
Example 2
- Input:
- nums = [0,0,0,0]
- Output:
- 3
- Explanation:
Every pair of cut positions works because all sums are 0: choose 2 of the 3 gaps, so the answer is 3.
Constraints
- 1 ≤ nums.length ≤ 106
- -109 ≤ nums[i] ≤ 109
Sums can exceed the 32-bit range, and the number of ways can exceed it too.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)