力扣刷题记录#数#1013将数组分成和相等的三个部分组
题目描述给定一个整数数组 A只有我们可以将其划分为三个和相等的非空部分时才返回 true否则返回 false。形式上如果我们可以找出索引 i1 j 且满足 (A[0] A[1] … A[i] A[i1] A[i2] … A[j-1] A[j] A[j-1] … A[A.length - 1]) 就可以将数组三等分。示例输出[0,2,1,-6,6,-7,9,1,2,0,1]输出true解释0 2 1 -6 6 - 7 9 1 2 0 1输入[0,2,1,-6,6,7,9,-1,2,0,1]输出false输入[3,3,6,5,-2,2,5,1,-9,4]输出true解释3 3 6 5 - 2 2 5 1 - 9 4解答解答1classSolution(object):defcanThreePartsEqualSum(self,A)::type A:List[int]:rtype:bool # 和 寻找数组中心索引 有点类似 total_sumsum(A)sub_sumtotal_sum/3iftotal_sum%3!0:returnFalse sum10# ind1用于记录第一组满足sub_sum和的子数组的最后一个索引 ind1Nonefori inrange(0,len(A)):sum1sum1A[i]ifsum1sub_sum:ind1ibreak# 如果ind1的值没有改变说明循环结束了都没有找到满足条件的子数组ifind1None:returnFalse sum20ind2None # ind2用于记录第二组满足sub_sum和的子数组的最后一个索引fori inrange(ind11,len(A)):sum2sum2A[i]ifsum2sub_sum:ind2ibreak# 如果ind2的值没有改变或ind2是最后一个元素此时第三个子数组就不存在了 # 说明没有找到满足条件的子数组ifind2None or ind2len(A)-1:returnFalse # 前两组之和都等于sub_sum则最后一组必然等于sub_sumreturnTrue解答2classSolution(object):defcanThreePartsEqualSum(self,A)::type A:List[int]:rtype:bool total_sumsum(A)sub_sumtotal_sum/3iftotal_sum%3!0:returnFalse # 和 寻找数组中心索引 有点类似 # 用双指针从两头开始查找 # 只需两头的子数组之和等于sub_sum则中间的必然满足 sum1A[0]sum3A[-1]i1jlen(A)-2flagFalsewhileij:ifsum1!sub_sum:sum1sum1A[i]i1ifsum3!sub_sum:sum3sum3A[j]j-1ifsum1sub_sum and sum3sub_sum:flagTruebreakreturnflag
