C++前缀和算法的应用：分割数组的最多方案数 原理源码测试用例

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);

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;
}