[数据结构与算法]1013. 将数组分成和相等的三个部分（c语言）

给你一个整数数组 arr，只有可以将其划分为三个和相等的 非空 部分时才返回?true，否则返回 false。

形式上，如果可以找出索引?i + 1 < j?且满足?(arr[0] + arr[1] + ... + arr[i] == arr[i + 1] + arr[i + 2] + ... + arr[j - 1] == arr[j] + arr[j + 1] + ... + arr[arr.length - 1])?就可以将数组三等分。

这道题我们首先可以直接对撞指针前后扫描求和最后比较中间值的和来判断是否符合要求

bool  canThreePartsEqualSum(int* arr, int arrSize){
         long long int sum1=0,sum2=0,sum3=0,count=0,i,j,k;         

         for(i=0;i<arrSize;i++)//首指针扫描与求和 
         {
             sum1=sum1+arr[i];
             for(j=arrSize-1;j>i;j--)//尾指针扫描与求和 
             {
                        sum2=sum2+arr[j];
                        if(sum1==sum2)
                        {
                           for(k=j-1;k>i;k--)//中间扫描求和 
                           {
                              sum3=sum3+arr[k];
                              count=1;//确保中间进行了扫描 
                           }
                           if(sum1==sum3 && (count==1 && i+1<j))//最后结果判断 
                           {
                               return true;
                           }
                           sum3=0;
                        }
             }
             sum2=0;
         }
         return false;                  
}

三个for过于繁杂，我们需要用数学进行优化.我们发现当满足条件时这个数组的和必须可以三等份，所以我们可以在首指针时只判断它和三分之一数组和的大小从而减少时间

bool  canThreePartsEqualSum(int* arr, int arrSize){
         long long int sum=0,sum1=0,sum2=0,sum3=0,count=0,i,j,k;   
		    
		for(i=0;i<arrSize;i++)
        {
              sum=sum+arr[i];
        }
        if(sum%3!=0)
        {
             return false;
        }
        sum=sum/3;      

         for(i=0;i<arrSize;i++)//首指针扫描与求和 
         {
             sum1=sum1+arr[i];
             if(sum1==sum)//第一层循环只需要判断一次 
             {
			  for(j=arrSize-1;j>i;j--)//尾指针扫描与求和 
              {
                        sum2=sum2+arr[j];
                        if(sum1==sum2)
                        {
                           for(k=j-1;k>i;k--)//中间扫描求和 
                           {
                              sum3=sum3+arr[k];
                              count=1;//确保中间进行了扫描 
                           }
                           if(sum1==sum3 && (count==1 && i+1<j))//最后结果判断 
                           {
                               return true;
                           }
                           sum3=0;
                        }
              }
              sum2=0;
          }
		 }
         return false;                  
}

执行用时：48 ms, 在所有?C?提交中击败了27.18%的用户

内存消耗：8.8 MB, 在所有?C?提交中击败了48.54%的用户

这个时候程序已经可以提交了，but！我们应该追求极限，这也是我们成长的刚需

从头开始加并且比较和的大小，一对满足条件就进行下一对的比较

bool  canThreePartsEqualSum(int* arr, int arrSize){
        long long int sum=0,sum1=0,sum2=0,sum3=0,count=0,i,j,k;         
        
        for(i=0;i<arrSize;i++)
        {
              sum=sum+arr[i];
        }
        if(sum%3!=0)//判断是否满足数学条件，缩短范围，只需要找是否三分满足即可 
        {
             return false;
        }
        sum=sum/3;//求平均值 
         for(i=0;i<arrSize;i++)//逐次相加并且判断 
         {
             sum1=sum1+arr[i];
             if(sum1==sum)//第一次比较，满足直接进入下一次 
             {
                 for(j=i+1;j<arrSize;j++)
               {
                        sum2=sum2+arr[j];
                        if(sum1==sum2)//第二次比较，满足直接进入下一次 
                        {
                           for(k=j+1;k<arrSize;k++)
                           {
                              sum3=sum3+arr[k];
                              count=1;
                           }
                           if(sum1==sum3 && count==1)//第三次比较，满足即出结果 
                           {
                               return true;
                           }
                        }
             }
         }
         }
         return false;                  
}

执行用时：40 ms, 在所有?C?提交中击败了94.17%的用户

内存消耗：8.7 MB, 在所有?C?提交中击败了92.23%的用户