LeetCode——将数组分割成和相等的子数组 C++

LeetCode——将数组分割成和相等的子数组 C++

 题目描述：截图取自LeetCode

         从该题目描述中0 < i, i + 1 < j, j + 1 < k < n - 1可以看出该数组至少有七个元素。且符合条件的数组一定满足如下结构：

 

        上图中的sum1~sum4中间不仅仅包含一个元素，也可能是多个元素。

        当我们知道了数组结构之后，可以逐步分析了，其实如果不考虑程序效率的话完全可以按照题目描述进行暴力求解，但是这道题在LeetCode上面的题目难度为困难，所以这道题一定不单单是暴力求解这么简单，其中需要用到剪枝的 *** 作来优化代码。

        本程序所用到的剪枝基本思想为从前往后先固定i的值，计算出sum1。然后确定j的值并计算sum2，如果sum2的值不等于sum1，则舍弃掉该j值（因为题目要求四个sum都相等才可以）。同理继续遍历确定k的值，直到找出结果。

        但是在提交代码的时候依旧遇到了大数组超时的情况。但是可以发现预设的大数组都是特殊数组（前后全是0）因为只有这种情况才可以在计算sum1和sum4时直接忽略掉而不影响最终结果，所以在代码中加入对这种情况的剪枝即可。

        完整代码如下：

bool splitArray(vector& nums) {
        long long int num=0,all=0;
        bool isok=false;
        int in,on;
        for(int i=0;i=0;i--){//忽略数组后方的大量0值
            if(nums[i]!=0){
                on=i;
                break;
            }
        }
        if(nums.size()<100)on=nums.size();
        if(!isok)return true;
        for(int i=in;i=nums.size())break;
            num=0;
            for(int ii=0;ii<=i-1;ii++)num+=nums[ii];//sum1(0~i-1)
            all=num;
            for(int j=i+2;j=nums.size())break;
                num=0;
                for(int ii=i+1;ii<=j-1;ii++)num+=nums[ii];//sum2(i+1~j-1)
                if(all!=num)continue;
                for(int k=j+2;k=nums.size()-1)break;
                    num=0;
                    for(int ii=j+1;ii<=k-1;ii++)num+=nums[ii];//sum3(j+1~k-1)
                    if(all!=num)continue;
                    num=0;
                    for(int ii=k+1;ii<=nums.size()-1;ii++)num+=nums[ii];//sum4(k+1~n-1)
                    if(all==num)return true;
                }
            }
        }
        return false;
    }