leetcode548 -- Split Array With Equal Sum (Locked)

leetcode548 -- Split Array With Equal Sum (Locked)

题目

题目的意思是给定一个数组, 就假设数组比较长,问是否存在`(i,j,k)`满足

`0<i,i+1<j,j+1<k<n-1`, 使得区间分成了四段,在四段上面的和

`[0,i-1], [i+1, j-1], [j+1,k-1], [k+1, n-1]`段的和相等,选出来的三个柱子并没有算在内。

并且区间的长度可以是为1的,比如`[1,2,1,2,1,2,1]`可以选`1,3,5`作为三个桩,那么四段里面每段都是1.

解答

这个题被locked, 在网上看的有些解答,首先是暴力search,是O(n^3)的,估计不太行,当数据量大的时候game over 了.

法一


class Solution {
public:
    bool splitArray(vector<int>& nums) {
        int n = nums.size();
        if (n < 7) {
            return false;
        }
        vector<int> sums(n, 0);
        sums[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            sums[i] = sums[i - 1] + nums[i];
        }
        for (int i = 1; i < n - 1; ++i) {
            for (int j = i + 2; j < n - 1; ++j) {
                for (int k = j + 2; k < n - 1; ++k) {
                    int part1 = sums[i - 1];                        // [0, i - 1]
                    int part2 = sums[j - 1] - sums[i];              // [i + 1, j - 1]
                    int part3 = sums[k - 1] - sums[j];              // [j + 1, k - 1]
                    int part4 = sums[nums.size() - 1] - sums[k];    // [k + 1, n - 1]
                    if (part1 == part2 && part2 == part3 && part3 == part4) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
};

法二,建立字典

class Solution {
public:
    bool splitArray(vector<int>& nums) {
        int n = nums.size();
        if (n < 7) {
            return false;
        }
        vector<int> sums(n, 0);
        sums[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            sums[i] = sums[i - 1] + nums[i];
        }
        for (int j = 3; j < n - 3; ++j) {         // j is the middle cut
            unordered_set<int> hash;
            for (int i = 1; i < j - 1; ++i) {
                if (sums[i - 1] == sums[j - 1] - sums[i]) {     // compare [0, i - 1] and [i + 1, j - 1]
                    hash.insert(sums[i - 1]);
                }
            }
            for (int k = j + 2; k < n - 1; ++k) {
                if (sums[n - 1] - sums[k] == sums[k - 1] - sums[j] && hash.count(sums[k - 1] - sums[j])) {    //这时候要看当前的这一段的,还要看之前有没有这样的和,有的话,才算是对的.
                    return true;
                }
            }
        }
        return false;
    }
};


打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦