Application of C++ prefix sum algorithm: maximum number of ways to split an array Principle source code test case

Basic knowledge points involved in this article

C++ algorithm: principles, source code and test cases of prefix sum, prefix product, prefix XOR including course videos

Title

You are given an array nums of integers starting from 0 and of length n. The number of options for splitting the array nums is defined as the number of pivots that meet the following two conditions:
1 <= pivot < n
nums[0] + nums[1] + … + nums[pivot – 1] == nums[pivot] + nums[pivot + 1] + … + nums[n – 1]
You are also given an integer k . You can change an element in nums to k or leave the array unchanged.
Please return the maximum number of ways to split nums so that the above two conditions are satisfied, under the premise that at most one element is changed.
Example 1:
Input: nums = [2,-1,2], k = 3
Output: 1
Explanation: An optimal solution is to change nums[0] to k. The array becomes [3,-1,2] .
There is a way to split an array:

  • pivot = 2 , we have the split [3,-1 | 2]: 3 + -1 == 2 .
    Example 2:
    Input: nums = [0,0,0], k = 1
    Output: 2
    Explanation: An optimal solution is not to modify the array.
    There are two ways to split an array:
  • pivot = 1 , we have split [0 | 0,0]: 0 == 0 + 0 .
  • pivot = 2 , we have split [0,0 | 0]: 0 + 0 == 0 .
    Example 3:
    Input: nums = [22,4,-25,-20,-15,15,-16,7,19,-10,0,-13,-14], k = -33
    Output: 4
    Explanation: An optimal solution is to change nums[2] to k. The array becomes [22,4,-33,-20,-15,15,-16,7,19,-10,0,-13,-14] .
    There are four ways to split an array.
    Parameter range:
    n == nums.length
    2 <= n <= 105
    -105 <= k, nums[i] <= 105

Analysis

Principle

If nums[0,p)-nums[p,m_c) is equal to 0, the condition is met. Modify nums[i]
i Add k to the left – nums[i]
i>=p Add k to the right – nums[i]

General process

First get the sum of all numbers in the initial state (unmodified).
Enumerate p, and put the left minus the right into mModifyRightLeftSubRight.
In the initial state, mModifyRightLeftSubRight[0] is the number of division plans.
Enumeration modifies nums[i].
If i is on the left Then the initial mModifyLeftLeftSubRight[-iSub] is the number of options
If i is on the right Then the initial mModifyRightLeftSubRight[iSub] is the number of options

Variable explanation

< /table>

Time complexity

The time complexity of both loops is O(n), so the total time complexity is O(n).

Code

Core code

class Solution {
public:
int waysToPartition(vector & amp; nums, int k) {
m_c = nums.size();
long long llTotal = std::accumulate(nums.begin(), nums.end(), 0LL);
std::unordered_map mModifyRightLeftSubRight;
//[0,p) left half, [p,m_c) right half
long long llR = 0; //llR is the sum of 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];//The number that can be split without changing any number
std::unordered_map mModifyLeftLeftSubRight;
//Modify 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;
};

Test cases

template
void Assert(const vector & amp; v1, const vector & amp; 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 slug;
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);

}

Old code in April 2023

class Solution {
public:
int waysToPartition(vector & amp; nums, int k) {
long long llSum = 0;
std::unordered_map mSumNum;//The sum of each prefix
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 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)
{//It is an odd number after the change
continue;
}

 int iCurRet = mSumNum[llNewSum / 2];
iCurRet + = mRightSumNum[llNewSum / 2 - (k - nums[i])];
iRet = max(iRet, iCurRet);
}
return iRet;
}

};

Extended reading

Video course

Effective learning: clear goals, timely feedback, stretching zone (appropriate difficulty), you can learn simple courses first, please go to CSDN Academy and listen to the explanation of Baiyin Lecturer (that is, I).
https://edu.csdn.net/course/detail/38771

how fast do you want

A battle has quickly formed. To share the worries of your boss, please learn C# onboarding training, C++ onboarding training and other courses.
https://edu.csdn.net/lecturer/6176

Related downloads

If you want to know the superior learning algorithm, please download the doc version of “Algorithm Book When You Hear the Defects”
https://download.csdn.net/download/he_zhidan/88348653
llTota nums and
mModifyLeftLeftSubRight; consistent with i < p, each scheme nums[0,p)-nums[p,m_c)
mModifyRightLeftSubRight Conforms to i>=p, each scheme nums[0,p)-nums[p,m_c)
What I want to say to everyone
It is a good wish to be happy when you hear the flaws. Discover problems and correct them early to save your boss money.
The origin of the Mohist name: everything is recorded in Mohism.
If the program is a one-stop process, then the algorithm is its key point

Test environment

Operating system: win7 Development environment: VS2019 C++ 17
Or operating system: win10 development environment:

VS2022 C++ 17