Given an array with n integers, you need to find if there are triplets (i, j, k) which satisfies following conditions:

0 < i, i + 1 < j, j + 1 < k < n - 1
Sum of subarrays (0, i - 1), (i + 1, j - 1), (j + 1, k - 1) and (k + 1, n - 1) should be equal.

where we define that subarray (L, R) represents a slice of the original array starting from the element indexed L to the element indexed R.

Example:

Input: [1,2,1,2,1,2,1]

Output: True

Explanation:

i = 1, j = 3, k = 5.

sum(0, i - 1) = sum(0, 0) = 1

sum(i + 1, j - 1) = sum(2, 2) = 1

sum(j + 1, k - 1) = sum(4, 4) = 1

sum(k + 1, n - 1) = sum(6, 6) = 1

Note:

1 <= n <= 2000.
Elements in the given array will be in range [-1,000,000, 1,000,000].

给一个数组，找出三个位置，使得数组被分为四段，使得每段之和相等，问存不存在这样的三个位置，注意三个位置上的数字不属于任何一段。

解法1: 暴力法，那就是三重循环，时间复杂度是O(n^3)，空间复杂度是O(n)。过不了大数据, TLE。

解法2: 采用空间换时间，从中间进行分割，然后在前半部分进行搜索，看看是不是可以找到和相同的划分，如果找到了，就将和加入哈希表中；然后再在后半部分进行搜索，如果找到了和相同的划分并且该和也存在于哈希表中，这说明找到了合适的i，j，k，可以将数组划分为和相同的四个部分，返回true。这样时间复杂度就降低成了O(n^2)。

解法3: 建立一个长度为数组长度的sum[i]，然后计算出每一个位置的它前面所有数字的和，这样就避免了以后大量的重复计算和的运算。然后计算i-j是否有满足1-i的和等于i-j, 有的话存到set里，避免重复计算。然后在计算位置k，是否也等于之前set里的值，如果有就返回True.

解法4: 用数组sums记录前n项和，在用字典idxs统计sums元素对应的下标列表，根据sums和idxs枚举满足(0, i - 1) == (i + 1, j - 1)条件的i，j。利用字典jlist记录子数组和对应的j值列表。最后遍历k，枚举jlist中子数组和(k + 1, n - 1)对应的j值，然后判断是否存在 (j + 1, k - 1) 与 (k + 1, n - 1) 相等

Java: 暴力， TLE

public class Solution {

    public int sum(int[] nums, int l, int r) {

        int summ = 0;

        for (int i = l; i < r; i++)

            summ += nums[i];

        return summ;

    }

    public boolean splitArray(int[] nums) {

        if (nums.length < 7)

            return false;

        for (int i = 1; i < nums.length - 5; i++) {

            int sum1 = sum(nums, 0, i);

            for (int j = i + 2; j < nums.length - 3; j++) {

                int sum2 = sum(nums, i + 1, j);

                for (int k = j + 2; k < nums.length - 1; k++) {

                    int sum3 = sum(nums, j + 1, k);

                    int sum4 = sum(nums, k + 1, nums.length);

                    if (sum1 == sum2 && sum3 == sum4 && sum2 == sum4)

                        return true;

                }

            }

        }

        return false;

    }

}

Java: 暴力，TLE

public class Solution {

    public boolean splitArray(int[] nums) {

        if (nums.length < 7)

            return false;

        int[] sum = new int[nums.length];

        sum[0] = nums[0];

        for (int i = 1; i < nums.length; i++) {

            sum[i] = sum[i - 1] + nums[i];

        }

        for (int i = 1; i < nums.length - 5; i++) {

            int sum1 = sum[i - 1];

            for (int j = i + 2; j < nums.length - 3; j++) {

                int sum2 = sum[j - 1] - sum[i];

                for (int k = j + 2; k < nums.length - 1; k++) {

                    int sum3 = sum[k - 1] - sum[j];

                    int sum4 = sum[nums.length - 1] - sum[k];

                    if (sum1 == sum2 && sum3 == sum4 && sum2 == sum4)

                        return true;

                }

            }

        }

        return false;

    }

}

Java: TLE

public class Solution {

    public boolean splitArray(int[] nums) {

        if (nums.length < 7)

            return false;

        int[] sum = new int[nums.length];

        sum[0] = nums[0];

        for (int i = 1; i < nums.length; i++) {

            sum[i] = sum[i - 1] + nums[i];

        }

        for (int i = 1; i < nums.length - 5; i++) {

            int sum1 = sum[i - 1];

            for (int j = i + 2; j < nums.length - 3; j++) {

                int sum2 = sum[j - 1] - sum[i];

                if (sum1 != sum2)

                    continue;

                for (int k = j + 2; k < nums.length - 1; k++) {

                    int sum3 = sum[k - 1] - sum[j];

                    int sum4 = sum[nums.length - 1] - sum[k];

                    if (sum3 == sum4 && sum2 == sum4)

                        return true;

                }

            }

        }

        return false;

    }

}

Java: Accepted

public class Solution {

    public boolean splitArray(int[] nums) {

        if (nums.length < 7)

            return false;

        int[] sum = new int[nums.length];

        sum[0] = nums[0];

        for (int i = 1; i < nums.length; i++) {

            sum[i] = sum[i - 1] + nums[i];

        }

        for (int j = 3; j < nums.length - 3; j++) {

            HashSet < Integer > set = new HashSet < > ();

            for (int i = 1; i < j - 1; i++) {

                if (sum[i - 1] == sum[j - 1] - sum[i])

                    set.add(sum[i - 1]);

            }

            for (int k = j + 2; k < nums.length - 1; k++) {

                if (sum[nums.length - 1] - sum[k] == sum[k - 1] - sum[j] && set.contains(sum[k - 1] - sum[j]))

                    return true;

            }

        }

        return false;

    }

}

Python:

# Time:  O(n^2)

# Space: O(n)

class Solution(object):

    def splitArray(self, nums):

        """

        :type nums: List[int]

        :rtype: bool

        """

        if len(nums) < 7:

            return False

        accumulated_sum = [0] * len(nums)

        accumulated_sum[0] = nums[0]

        for i in xrange(1, len(nums)):

            accumulated_sum[i] = accumulated_sum[i-1] + nums[i]

        for j in xrange(3, len(nums)-3):

            lookup = set()

            for i in xrange(1, j-1):

                if accumulated_sum[i-1] == accumulated_sum[j-1] - accumulated_sum[i]:

                    lookup.add(accumulated_sum[i-1])

            for k in xrange(j+2, len(nums)-1):

                if accumulated_sum[-1] - accumulated_sum[k] == accumulated_sum[k-1] - accumulated_sum[j] and \

                   accumulated_sum[k - 1] - accumulated_sum[j] in lookup:

                    return True

        return False

Python:

class Solution(object):

    def splitArray(self, nums):

        """

        :type nums: List[int]

        :rtype: bool

        """

        size = len(nums)

        sums = [0] * (size + 1)

        for x in range(size):

            sums[x + 1] += sums[x] + nums[x]

        idxs = collections.defaultdict(list)

        for x in range(size):

            idxs[sums[x + 1]].append(x)

        jlist = collections.defaultdict(list)

        for i in range(1, size):

            for j in idxs[2 * sums[i] + nums[i]]:

                if i < j < size:

                    jlist[sums[i]].append(j + 1)

        for k in range(size - 2, 0, -1):

            for j in jlist[sums[size] - sums[k + 1]]:

                if j + 1 > k: continue

                if sums[k] - sums[j + 1] == sums[size] - sums[k + 1]:

                    return True

        return False

C++:

class Solution {

public:

    bool splitArray(vector<int>& nums) {

        if (nums.size() < 7) return false;

        int n = nums.size();

        vector<int> sums = nums;

        for (int i = 1; i < n; ++i) {

            sums[i] = sums[i - 1] + nums[i];

        }

        for (int j = 3; j < n - 3; ++j) {

            unordered_set<int> s;

            for (int i = 1; i < j - 1; ++i) {

                if (sums[i - 1] == (sums[j - 1] - sums[i])) {

                    s.insert(sums[i - 1]);

                }

            }

            for (int k = j + 1; k < n - 1; ++k) {

                int s3 = sums[k - 1] - sums[j], s4 = sums[n - 1] - sums[k];

                if (s3 == s4 && s.count(s3)) return true;

            }

        }

        return false;

    }

};

C++:

class Solution {

public:

    bool splitArray(vector<int>& nums) {

        if (nums.size() < 7) return false;

        int n = nums.size(), target = 0;

        int sum = accumulate(nums.begin(), nums.end(), 0);

        for (int i = 1; i < n - 5; ++i) {

            if (i != 1 && nums[i] == 0 && nums[i - 1] == 0) continue;

            target += nums[i - 1];

            if (helper(nums, target, sum - target - nums[i], i + 1, 1)) {

                return true;

            }

        }

        return false;

    }

    bool helper(vector<int>& nums, int target, int sum, int start, int cnt) {

        if (cnt == 3) return sum == target;

        int curSum = 0, n = nums.size();

        for (int i = start + 1; i < n + 2 * cnt - 5; ++i) {

            curSum += nums[i - 1];

            if (curSum == target && helper(nums, target, sum - curSum - nums[i], i + 1, cnt + 1)) {

                return true;

            }

        }

        return false;

    }

C++: 暴力+优化　　

class Solution {

public:

    bool splitArray(vector<int>& nums) {

        int n = nums.size();

        vector<int> sums = nums;

        for (int i = 1; i < n; ++i) {

            sums[i] = sums[i - 1] + nums[i];

        }

        for (int i = 1; i <= n - 5; ++i) {

            if (i != 1 && nums[i] == 0 && nums[i - 1] == 0) continue;

            for (int j = i + 2; j <= n - 3; ++j) {

                if (sums[i - 1] != (sums[j - 1] - sums[i])) continue;

                for (int k = j + 2; k <= n - 1; ++k) {

                    int sum3 = sums[k - 1] - sums[j];

                    int sum4 = sums[n - 1] - sums[k];

                    if (sum3 == sum4 && sum3 == sums[i - 1]) {

                        return true;

                    }

                }

            }

        }

        return false;

    }

};

类似题目：

Split an array into two equal Sum subarrays

All LeetCode Questions List 题目汇总

巴特西

[LeetCode] 548. Split Array with Equal Sum 分割数组成和相同的子数组

All LeetCode Questions List 题目汇总

最新文章

热门文章