题目解析
题目中要求把一个数组分割成具有相等和的子数组，即划分出一些子数组，使得每个子数组的元素和相等。问题转化为判断是否有一种划分方法满足这样的条件。
由于每个子数组的元素和相等，所以我们可以先求出整个数组的和，假设为sum。那么，如果能找到一种划分方法，使得每个子数组的元素和为x，那么必然有sum% x=0。
同时，如果我们能找到一种划分方法，满足每个子数组的元素和为x，那么也就意味着可以找到一种划分方法，使得每k个子数组的元素和为kx。因此，我们只需要在数组中寻找一些长度为k的连续子序列，使得其元素和为kx即可。
方法一：暴力枚举
算法思路
首先，我们可以枚举每个子数组的长度k，从1到n。然后，对于每个长度为k的子数组，判断其元素和是否为x。
代码实现
int cnt=0;
for(int k=1;k<=n;k++){
if(sum%k) continue;//如果不能整除就跳过
int x=sum/k;//子数组的和
int s=0;
bool flag=true;
for(int i=0;i
s+=a[i];
if(s>x){
flag=false;
break;
}else if(s==x){
s=0;
}
}
if(flag) cnt++;
}
算法分析
时间复杂度：枚举每个子数组的长度需要花费O(n)的时间，而判断每个子数组的元素和是否为x也需要花费O(n)的时间，总时间复杂度为O(n^2)。虽然这种方法的时间复杂度比较高，但由于其思路简单，所以在k比较小的情况下仍然可以使用。
方法二：前缀和+哈希表
算法思路
对于每个长度为k的子数组，其元素和为x，则我们可以得到一个等式:
sum[i]-sum[j-1]=k*x;j<=i
其中,sum[i]表示前i个元素的和。我们可以通过枚举j，来枚举所有长度为k的子数组，并计算其元素和是否为x。
但是，这样的做法时间复杂度为O(n^2)，无法通过本题。我们需要优化它。可以将前缀和看做一个整体，然后对于每个子数组的元素和x，我们可以得到一个等式:
sum[i]-k*x=sum[j-1]
其中，k为子数组的长度。我们可以将其转化为如下形式：
sum[i]-sum[j-1]=k*x
这样，我们就可以使用哈希表来优化了。
代码实现
int cnt=0;
for(int k=1;k<=n;k++){
if(sum%k) continue;
int x=sum/k;
unordered_map<int,int> mp;
mp[0]=1;//从前往后，即j从0开始
int s=0;
for(int i=0;i
s+=a[i];
if(mp.count(s-x*k)){
cnt+=mp[s-x*k];//累加次数
}
mp[s]++;
}
}
算法分析
时间复杂度：枚举每个子数组的长度需要花费O(n)的时间；对于每个长度为k的子数组，我们需要计算其元素和和查找哈希表中是否存在(和-kx)这个前缀和，其中每个前缀和都只会被扫描一次，所以这一步的时间复杂度为O(n)。总时间复杂度为O(n^2)。
方法三：二分答案
算法思路
我们也可以使用二分答案的方法来解决这一问题。对于每个子数组的元素和x，我们可以二分其可能的值。具体来说，我们在区间[1,sum]中二分，假设当前二分到的值为mid，则我们需要判断是否存在一种划分方法，使得每个子数组的元素和为mid。
我们可以遍历原数组a，并对于每个位置i，求出以i结尾的长度不超过k的子数组的和。如果这个值等于mid，说明我们可以从i+1继续开始寻找下一个长度为不超过k的子数组。如果这个值大于mid，则说明我们需要将i向右移动一位，因为原先的这个子数组不满足要求。如果这个值小于mid，则说明长度不超过k的子数组的和已经超出了mid，则需要减小mid。
代码实现
int cnt=0;
int l=1,r=sum;
while(l<=r){
int mid=(l+r)/2;
int s=0,num=1;
bool flag=true;
for(int i=0;i<n;i++){
if(a[i]>mid){
flag=false;
break;
}
s+=a[i];
if(s>mid){
num++;
s=a[i];//新的子数组的和
}
}
if(!flag||num>k){//不存在划分，说明需要增加mid
l=mid+1;
}else{
cnt++;
r=mid-1;//可能存在多种方案
}
}
算法分析
时间复杂度：二分答案需要O(log(sum))的时间；遍历数组a需要O(n)的时间，因此总时间复杂度为O(n*log(sum))。
总结
本文介绍了三种解决本问题的算法：暴力枚举、前缀和+哈希表、二分答案。三种算法的核心思想都是相同的：找到一些长度为k的子数组，使得每个子数组的元素和相等。其中，暴力枚举可以说是最容易想到的，但时间复杂度不够优秀；前缀和+哈希表可以进行优化，但占用的空间比较大；二分答案是一种次优算法，它的时间复杂度介于前两种算法之间。