题目地址:https://leetcode.com/problems/partition-array-into-three-parts-with-equal-sum/

题目描述

Given an array A of integers, return true if and only if we can partition the array into three non-empty parts with equal sums.

Formally, we can partition the array if we can find indexes i+1 < j with (A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1])

Example 1:

Input: [0,2,1,-6,6,-7,9,1,2,0,1]
Output: true
Explanation: 0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1

Example 2:

Input: [0,2,1,-6,6,7,9,-1,2,0,1]
Output: false

Example 3:

Input: [3,3,6,5,-2,2,5,1,-9,4]
Output: true
Explanation: 3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4

Note:

1、 3<=A.length<=50000;
2、 -10000<=A[i]<=10000;

题目大意

给定一个数组能不能分成和相等的连续三部分。每部分至少一个数字。

解题方法

这个题其实很简单,有同学没做出来的原因是把题目的连续条件给忘了、按照回溯法做这个题的话,看到数组A的长度是50000肯定会超时。

既然是连续相等的三部分,那么可以先求出数组总体的和_sum,除以3就得到了每部分的和target。易知这题的时间复杂度要求是O(N),所以当我们进行搜索的时候,只要找到一个连续子子数组的和是target,那么就重新开始计算后面部分的和,统计有多少个连续子数组的和是target。

当我们遍历完成一遍的时候,如果count大于等于3,说明一定可以分成连续相等的三部分。

这里解释下为什么需要count >= 3,因为如果有0出现或者有多个部分的和都是0的话,那么count可以大于3。比如[0,0,0,0,0]的测试用例,count是5,但是也可以分为三个和相等的部分。例如[1, -1, 1, -1, 1, -1, 0],count是4,也可以分为三个和相等的部分。

Python代码如下:

class Solution(object):
    def canThreePartsEqualSum(self, A):
        """
        :type A: List[int]
        :rtype: bool
        """
        _sum = sum(A)
        if _sum % 3 != 0:
            return False
        target = _sum / 3
        count = 0
        cursum = 0
        for a in A:
            cursum += a
            if cursum == target:
                count += 1
                cursum = 0
        return count >= 3

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

参考资料:https://leetcode.com/problems/partition-array-into-three-parts-with-equal-sum/discuss/260885/C%2B%2B-6-lines-O(n)-target-sum

2022

DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有

本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发