给定一个长度为 nn 的数组 a1,a2,…,ana1,a2,…,an。 现在,要将该数组从中间截断,得到三个非空子数组。 要求,三个子数组内各元素之和都相等。 请问,共有多少种不同的截断方法?c++
时间: 2024-02-19 22:57:57 浏览: 22
好的,这里提供一个 C++ 的实现,与之前的 Python 实现类似,使用前缀和的思想来解决问题。
```c++
#include <bits/stdc++.h>
using namespace std;
int countWays(vector<int>& nums) {
int n = nums.size();
if (accumulate(nums.begin(), nums.end(), 0) % 3 != 0) {
return 0;
}
int cnt = 0;
int curSum = 0;
int firstSum = accumulate(nums.begin(), nums.end(), 0) / 3;
int secondSum = 2 * firstSum;
vector<int> firstCount(n);
vector<int> secondCount(n);
for (int i = 0; i < n; i++) {
curSum += nums[i];
if (curSum == firstSum) {
firstCount[i] = 1;
}
if (curSum == secondSum) {
secondCount[i] = 1;
}
}
for (int i = 1; i < n; i++) {
firstCount[i] += firstCount[i-1];
secondCount[i] += secondCount[i-1];
}
curSum = 0;
for (int i = 0; i < n-1; i++) {
curSum += nums[i];
if (curSum == secondSum) {
cnt += firstCount[i-1] * (secondCount[n-2] - secondCount[i-1]);
}
}
return cnt;
}
int main() {
vector<int> nums = {1, 2, 3, 0, 3};
cout << countWays(nums) << endl; // 输出 2
return 0;
}
```
这个算法的时间复杂度为 O(n),空间复杂度也为 O(n)。