每日一题-11

题目描述

将数组分成和相等的三个部分
给你一个整数数组 A，只有可以将其划分为三个和相等的非空部分时才返回 true，否则返回 false。

形式上，如果可以找出索引 i+1 < j 且满足 (A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1]) 就可以将数组三等分。

示例 1：

输出：[0,2,1,-6,6,-7,9,1,2,0,1]
输出：true
解释：0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1
示例 2：

输入：[0,2,1,-6,6,7,9,-1,2,0,1]
输出：false
示例 3：

输入：[3,3,6,5,-2,2,5,1,-9,4]
输出：true
解释：3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4

提示：

3 <= A.length <= 50000
-10^4 <= A[i] <= 10^4

解题思路

1.首先计算总和，判断是否可以三等分
然后计算是否刚好有三部分等于总和//3
由于题目要求的是连续子数组，所以可以先把第一部分和第二部分加出来，剩下的就是第三部分（直接求和）
需要注意的是一个例子：[10,-10,10,-10,10,-10,10,-10]
这个例子总和等于0，也可以等分为三部分([10,-10],[10,-10],[10,-10,10,-10])
但是，它也可以等分为四部分([10,-10],[10,-10],[10,-10],[10,-10]),所以已经出现了tmp==3的时候，就直接退出循环。或者直接判断第三部分的求和与总和//3的比较，返回True或False,或者最后tmp>=3

2.双指针，计算两边部分是否等于总和//3

代码

class Solution:
    def canThreePartsEqualSum(self, A: List[int]) -> bool:
        if len(A)<3:
            return False

        ans = sum(A)
        if ans%3:
            return False
        else:
            r = ans//3
            s = 0
            tmp = 0
            for i in range(len(A)):
                if tmp==3:
                    break
                if tmp==2:
                    s = sum(A[i:])
                else:
                    s += A[i]

                if s==r:
                    s = 0
                    tmp+=1

        return tmp==3

双指针

class Solution:
    def canThreePartsEqualSum(self, A: List[int]) -> bool:
        if len(A)<3:
            return False

        ans = sum(A)
        if ans%3:
            return False
        else:
            r = ans//3
            leftSum = A[0]
            rightSum = A[-1]
            left = 0
            right = len(A)-1
            while left+1 < right:#防止数组等分成两部分
                if leftSum == r and rightSum == r:
                    return True
                if leftSum != r:
                    left+=1
                    leftSum += A[left]
                if rightSum != r:
                    right -= 1
                    rightSum += A[right]

        return False