leecode 1712. 将数组分成三个子数组的方案数
简述思路
其实 这个思路 也是参考了一下 别人写的讲解
一开始是用的前缀和加遍历搜索 。
然后就是 超时 !!
后来准备用二分查找,但是对于边界记录和一般的二分查找会有点不同。不太易于理解。
后来就看了下别人写的讲解,觉得这个方法,高效且容易理解。
具体细节看代码
class Solution {
public int waysToSplit(int[] nums) {
int len=nums.length;
int [] sum= new int[len];
int i;
sum[0]=nums[0];
for (i=1;i<len;i++)
{
sum[i]=sum[i-1]+nums[i];
}
int SUM=0;
int indexa=1,index2=1;
for(i=0;i<len-2;i++)
{
if (indexa<i+1){
indexa=i+1;
}
while (indexa<len-1 && sum[indexa]-sum[i]<sum[i]){
indexa++;
}
if(indexa==len-1){
break;
}
if (indexa>index2){
index2=indexa;
}
while(index2<len-1 && sum[len-1]-sum[index2]>=sum[index2]-sum[i]){
index2++;
}
SUM=(SUM+(index2-indexa))%1000000007;
}
return SUM;
}
}
提交: