【C++二分查找 前缀和】1712. 将数组分成三个子数组的方案数|2078
本文涉及的基础知识点
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
C++二分查找
LeetCode1712. 将数组分成三个子数组的方案数
我们称一个分割整数数组的方案是 好的 ，当它满足：
数组被分成三个 非空 连续子数组，从左至右分别命名为 left ， mid ， right 。
left 中元素和小于等于 mid 中元素和，mid 中元素和小于等于 right 中元素和。
给你一个 非负 整数数组 nums ，请你返回 好的 分割 nums 方案数目。由于答案可能会很大，请你将结果对 109 + 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 <= 105
0 <= nums[i] <= 104
二分查找+前缀和
令第二段是nums[i…j]。
枚举i，计算j。
nums[i…j] >= nums[0…i-1]即：
preSum[j+1]- preSum[i] >= preSum[i] ,即preSum[j+1] >= preSum[i]2
nums[j+1…] >= nums[i…j]即：
preSum.back() - preSum[j+1] >= preSum[j+1]- preSum[i]
preSub.back()+preSum[i] >= 2preSum[j+1]
preSum[j+1] <= (preSub.back()+preSum[i])/2
preSum[j+1] < (preSum.back()+preSum[i])/2+1 注意：nums可能存在为0的元素。
int j1 = lower_bound(preSum.begin(), preSum.end(), preSum[i] * 2)- preSum.begin();
j1 = max(j1, i + 1);
int j2 = lower_bound(preSum.begin(), preSum.end(), (preSum.back() + preSum[i]) / 2 + 1) - preSum.begin();
j2 = min(j2, (int)nums.size() );
j+1的合法范围是：[j1,j2)
同时要确保 j >= i ，j < n-1
代码
核心代码
class Solution {
public:
int waysToSplit(vector<int>& nums) {
vector<int> preSum(1);
for (const auto& n : nums) {
preSum.emplace_back(n + preSum.back());
}
long long ret = 0;
for (int i = 1; i + 1 < nums.size(); i++) {
int j1 = lower_bound(preSum.begin(), preSum.end(), preSum[i] * 2)- preSum.begin();
j1 = max(j1, i + 1);
int j2 = lower_bound(preSum.begin(), preSum.end(), (preSum.back() + preSum[i]) / 2 + 1) - preSum.begin();
j2 = min(j2, (int)nums.size() );
ret += max(0,(j2 - j1));
}
return ret%((int)1e9+7);
}
};
单元测试
vector<int> nums;
TEST_METHOD(TestMethod11)
{
nums = { 1,1,1 };
auto res = Solution().waysToSplit(nums);
AssertEx(1, res);
}
TEST_METHOD(TestMethod12)
{
nums = { 1,2,2,2,5,0 };
auto res = Solution().waysToSplit(nums);
AssertEx(3, res);
}
TEST_METHOD(TestMethod13)
{
nums = { 3,2,1 };
auto res = Solution().waysToSplit(nums);
AssertEx(0, res);
}
TEST_METHOD(TestMethod14)
{
nums = { 0,3,3};
auto res = Solution().waysToSplit(nums);
AssertEx(1, res);
}
TEST_METHOD(TestMethod15)
{
nums = { 2,8,10,0,2 };
auto res = Solution().waysToSplit(nums);
AssertEx(1, res);
}
TEST_METHOD(TestMethod16)
{
nums.assign(100000,0);
auto res = Solution().waysToSplit(nums);
AssertEx(999849973, res);
}
TEST_METHOD(TestMethod17)
{
nums.assign(4, 0);
auto res = Solution().waysToSplit(nums);
AssertEx(3, res);
}
扩展阅读
| 我想对大家说的话 |
|---|
| 工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作 |
| 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
| 失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
原文地址：https://blog.csdn.net/he_zhidan/article/details/141637807
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！