本文涉及的基础知识点
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
题目
给你一个下标从 0 开始且长度为 n 的整数数组 nums 。分割 数组 nums 的方案数定义为符合以下两个条件的 pivot 数目：
1 <= pivot < n
nums[0] + nums[1] + … + nums[pivot - 1] == nums[pivot] + nums[pivot + 1] + … + nums[n - 1]
同时给你一个整数 k 。你可以将 nums 中 一个 元素变为 k 或 不改变 数组。
请你返回在 至多 改变一个元素的前提下，最多 有多少种方法 分割 nums 使得上述两个条件都满足。
示例 1：
输入：nums = [2,-1,2], k = 3
输出：1
解释：一个最优的方案是将 nums[0] 改为 k 。数组变为 [3,-1,2] 。
有一种方法分割数组：
- pivot = 2 ，我们有分割 [3,-1 | 2]：3 + -1 == 2 。
示例 2：
输入：nums = [0,0,0], k = 1
输出：2
解释：一个最优的方案是不改动数组。
有两种方法分割数组： - pivot = 1 ，我们有分割 [0 | 0,0]：0 == 0 + 0 。
- pivot = 2 ，我们有分割 [0,0 | 0]: 0 + 0 == 0 。
示例 3：
输入：nums = [22,4,-25,-20,-15,15,-16,7,19,-10,0,-13,-14], k = -33
输出：4
解释：一个最优的方案是将 nums[2] 改为 k 。数组变为 [22,4,-33,-20,-15,15,-16,7,19,-10,0,-13,-14] 。
有四种方法分割数组。
参数范围：
n == nums.length
2 <= n <= 105
-105 <= k, nums[i] <= 105
分析
原理
nums[0,p)-nums[p,m_c) 如果等于0，则符合条件。修改nums[i]
| i <p | 左边增加 k - nums[i] |
| i>=p | 右边增加 k - nums[i] |
大致流程
先获取初始状态（未修改）所有数的和。
枚举p，左边减右边的放到mModifyRightLeftSubRight中。
初始状态下，mModifyRightLeftSubRight[0]就是分割方案数。
枚举修改nums[i]。
| 如果i在左边 | 则初始mModifyLeftLeftSubRight[-iSub]就是方案数 |
| 如果i在右边 | 则初始mModifyRightLeftSubRight[iSub]就是方案数 |
变量解释
| llTota | nums的和 |
| mModifyLeftLeftSubRight; | 符合i < p，各方案nums[0,p)-nums[p,m_c) |
| mModifyRightLeftSubRight | 符合i>=p，各方案nums[0,p)-nums[p,m_c) |
时间复杂度
两次循环，时间复杂度都是O(n)，故总时间复杂度是O(n)。
代码
核心代码
class Solution { public: int waysToPartition(vector& nums, int k) { m_c = nums.size(); long long llTotal = std::accumulate(nums.begin(), nums.end(), 0LL); std::unordered_map<long, int> mModifyRightLeftSubRight; //[0,p)左半部分，[p,m_c)右半部分 long long llR = 0;//llR是nums[p,m_c)的和 for (int p = m_c - 1; p > 0; p–) { llR += nums[p]; const long long llLeft = llTotal - llR; mModifyRightLeftSubRight[llLeft - llR]++; } int iRet = mModifyRightLeftSubRight[0];//不改变任何数，能拆分的数量 std::unordered_map<long, int> mModifyLeftLeftSubRight; //修改nums[p] llR = 0; for (int i = m_c - 1; i >= 0; i–) { int iSub = (k - nums[i]); const int cur = mModifyRightLeftSubRight[iSub]+ mModifyLeftLeftSubRight[-iSub]; iRet = max(iRet, cur); llR += nums[i]; const long long llLeft = llTotal - llR; mModifyRightLeftSubRight[llLeft - llR]–; mModifyLeftLeftSubRight[llLeft - llR]++; } return iRet; } int m_c; };
测试用例
template void Assert(const vector& v1, const vector& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { assert(v1[i] == v2[i]); } } template void Assert(const T& t1, const T& t2) { assert(t1 == t2); } int main() { Solution slu; vector nums; int k; int res; nums = { 0,0,0 }; k = 1; res = slu.waysToPartition(nums, k); Assert(2, res); nums = { 0,0,0,0 }; k =3; res = slu.waysToPartition(nums, k); Assert(3, res); nums = { -2, -1, 3, 4, 5 }; k = 3; res = slu.waysToPartition(nums, k); Assert(0, res); nums = { -2, -1, 3, 4, 5 }; k = 2; res = slu.waysToPartition(nums, k); Assert(0, res); nums = { -2, -1, 3, 4, 5 }; k = -3; res = slu.waysToPartition(nums, k); Assert(0, res); nums = { -1, -1, 3, 4, 5 }; k = -3; res = slu.waysToPartition(nums, k); Assert(1, res); nums = { -1,3 }; k = 3; res = slu.waysToPartition(nums, k); Assert(1, res); nums = { 5,4,3 }; k = 8; res = slu.waysToPartition(nums, k); Assert(0, res); nums = { 5,4,3 }; k = 1; res = slu.waysToPartition(nums, k); Assert(1, res);
nums = { 5,4,3 }; k = 7; res = slu.waysToPartition(nums, k); Assert(1, res); nums = { 3,5,4 }; k = 1; res = slu.waysToPartition(nums, k); Assert(1, res); nums = { 3,5,4 }; k = 1; res = slu.waysToPartition(nums, k); Assert(1, res); nums = { 3,5,4 }; k = 0; res = slu.waysToPartition(nums, k); Assert(0, res); //CConsole::Out(res);
}
2023年4月旧代码
class Solution { public: int waysToPartition(vector& nums, int k) { long long llSum = 0; std::unordered_map<long long, int> mSumNum;//各前缀和数量 vector vSum; for (int i = 0; i < nums.size(); i++) { llSum += nums[i]; vSum.emplace_back(llSum); if (i + 1 < nums.size()) { mSumNum[llSum]++; } } int iRet = 0; if (0 == llSum % 2) { iRet += mSumNum[llSum / 2]; } const long long llNewSum = llSum + k - nums.back(); if (0 == llNewSum % 2) { iRet =max(iRet, mSumNum[llNewSum / 2]); } std::unordered_map<long long, int> mRightSumNum; for (int i = nums.size() - 2; i >= 0; i–) { const long long& llCurSum = vSum[i]; mSumNum[llCurSum]–; mRightSumNum[llCurSum]++; const long long llNewSum = llSum + k - nums[i]; if (llNewSum & 1) {//改变后是奇数 continue; }
int iCurRet = mSumNum[llNewSum / 2]; iCurRet += mRightSumNum[llNewSum / 2 - (k - nums[i])]; iRet = max(iRet, iCurRet); } return iRet; }
};
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 鄙人想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 墨家名称的来源：有所得以墨记之。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：
VS2022 C++17
