Split Array With Equal Sum

发表于 | 分类于

Split Array With Equal Sum(四段和相等的切分点)

题目描述：

给定一个长度为n的数组；要求找到3个切分点i,j,k满足如下要求：

  • 0 < i, i + 1 < j, j + 1 < k < n - 1;
  • sum[0, i - 1] = sum[i + 1, j - 1] = sum[j + 1, k - 1] = sum[k + 1, n - 1]

例子：

输入时[1,2,1,2,1,2,1]的符合题意的切分点是[1,3,5]

解题思路：

首先为了计算切分的段落和，我们可以构建一个累加和数组，其中sum[i]代表数组[0,i]的数据和，这样可以计算任意段落的和了；然后我们可以遍历i,j,k不同的位置用来判断是否满足条件即可。需要注意的点有因为数组中可以有负数，所以不能根据累加和肯定递增，如果当前位置不满足条件后面肯定不满足这个想法来剪枝；另外测试用例中包含了大量的0；对于计算累加和的时间消耗太多；所以需要针对这个情况做累加和计算的改进。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    bool splitArray(vector<int>& nums) {
        if(nums.size() < 6) return false;
        vector<int> sum;
        int prev = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 0 && i > 0 && nums[i - 1] == 0)  continue;
            //针对连续0的情况，累加和计算的改进
            prev += nums[i];
            sum.push_back(prev);
        }
        for (int i = 1; i < sum.size() - 5; i++){
            int sum1 = sum[i - 1];
            for (int j = i + 2; j < sum.size() - 3; j++){
                int sum2 = sum[j - 1] - sum[i];
                if (sum1 != sum2) continue;
                for (int k = j + 2; k < sum.size() - 1; k++){
                    int sum3 = sum[k - 1] - sum[j];
                    int sum4 = sum[sum.size() - 1] - sum[k];
                    if (sum2 == sum3 && sum3 == sum4)
                        return true;
                }
            }//遍历i,j,k用来寻找满足条件的切分位置
        }
        return false;
        
    }
};