A split of an integer array is good if:
- The array is split into three non-empty contiguous subarrays – named
left
,mid
,right
respectively from left to right. - The sum of the elements in
left
is less than or equal to the sum of the elements inmid
, and the sum of the elements inmid
is less than or equal to the sum of the elements inright
.
Given nums
, an array of non-negative integers, return the number of good ways to split nums
. As the number may be too large, return it modulo 109 + 7
.
Example 1:
Input: nums = [1,1,1] Output: 1 Explanation: The only good way to split nums is [1] [1] [1].
Example 2:
Input: nums = [1,2,2,2,5,0] Output: 3 Explanation: There are three good ways of splitting nums: [1] [2] [2,2,5,0] [1] [2,2] [2,5,0] [1,2] [2,2] [5,0]
Example 3:
Input: nums = [3,2,1] Output: 0 Explanation: There is no good way to split nums.
Constraints:
3 <= nums.length <= 105
0 <= nums[i] <= 104
Solution 1: Prefix Sum + Binary Search
We split the array into [0 … i] [i + 1… j] [j + 1 … n – 1]
we can use binary search to find the min and max of j for each i.
s.t. sum(0 ~ i) <= sums(i + 1 ~j) <= sums(j + 1 ~ n – 1)
min is lower_bound(2 * sums(0 ~ i))
max is upper_bound(sums(0 ~ i) + (total – sums(0 ~ i)) / 2)
Time complexity: O(nlogn)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua class Solution { public: int waysToSplit(vector<int>& nums) { constexpr int kMod = 1e9 + 7; const int n = nums.size(); for (int i = 1; i < n; ++i) nums[i] += nums[i - 1]; const int total = nums.back(); long ans = 0; // [0 .. i] [i + 1 ... j] [j + 1 ... n - 1] for (int i = 0, left = 0; i < n; ++i) { auto it1 = lower_bound(begin(nums) + i + 1, end(nums), 2 * nums[i]); auto it2 = upper_bound(begin(nums), end(nums) - 1, nums[i] + (total - nums[i]) / 2); if (it2 <= it1) continue; ans += it2 - it1; } return ans % kMod; } }; |
Solution 2: Prefix Sum + Two Pointers
The right end of the middle array is in range [j, k – 1] and there are k – j choices.
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua class Solution { public: int waysToSplit(vector<int>& nums) { constexpr int kMod = 1e9 + 7; const int n = nums.size(); for (int i = 1; i < n; ++i) nums[i] += nums[i - 1]; const int total = nums.back(); long ans = 0; for (int i = 0, j = 0, k = 0; i < n; ++i) { j = max(j, i + 1); while (j < n - 1 && nums[j] < 2 * nums[i]) ++j; k = max(k, j); while (k < n - 1 && 2 * nums[k] <= nums[i] + total) ++k; ans += (k - j); } return ans % kMod; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment