[ 力扣活动0311 ] 1013. 将数组分成和相等的三个部分

题目描述

给你一个整数数组 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

解题思路

我的思路

三等分数组，只需要每一等分 == 数组和/3 即可。

不过这样会有漏洞

1.比如对于数组 [1,-1,1,-1]，每一等分 == 0 ，满足我提出的条件，但是不对的

2.对于数组 [10,-10,10,-10,10,-10,10,-10]，按照我的思路下来，就有四等分。也是不对的

3.对于太大的数组超时。。。

class Solution(object):
    def canThreePartsEqualSum(self, A):
        """
        :type A: List[int]
        :rtype: bool
        """
        
        if sum(A)%3!=0:
            return False
        count=0
        index=0
        ext = 0 
        while index<len(A):
            count+=A[index]
            #每次加到目标值就表示这一等分没问题
            #用ext来表示共有几等分
            if count == sum(A)/3:
                count = 0
                ext+=1
            index+=1
        #特殊的样例过不了。。。
        if count or ext<3:
            return False
        return True

View Code

题解1

头尾指针向中间逼近，只需要头尾满足两段，中间一定满足第三段。

1.注意while循环的条件

2.注意指针的位置

class Solution(object):
    def canThreePartsEqualSum(self, A):
        """
        :type A: List[int]
        :rtype: bool
        """
        if sum(A)%3!=0:
            return False
        a,b = 0,len(A)-1
        # 这里先给变量赋了初始值，以防止a,b超出范围
        acount , bcount = A[0],A[-1]
        tar = sum(A)//3
        while a+1<b:
            if acount == tar and bcount == tar:
                return True
            if acount!=tar:
                #保证a，b 的范围正确
                a+=1
                acount+=A[a]
            if bcount!=tar:
                b-=1
                bcount+=A[b]
        return False

总结

1. while循环选择 a+1 < b 作为条件是为了空出中间的一段。

2. acount , bcount = A[0] , A[-1]，先赋初始值，再迭加，防止 a,b “冲出跑道”

3.tar = sum(A) // 3 ：除法向下取整技巧