LeetCode 1013. 将数组分成和相等的三个部分 Partition Array Into Three Parts With Equal Sum

简介: LeetCode 1013. 将数组分成和相等的三个部分 Partition Array Into Three Parts With Equal Sum

LeetCode 1013. 将数组分成和相等的三个部分 Partition Array Into Three Parts With Equal Sum


Table of Contents

一、中文版

二、英文版

三、My answer

四、解题报告

一、中文版

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

二、英文版

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: A = [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: A = [0,2,1,-6,6,7,9,-1,2,0,1]
Output: false
Example 3:
Input: A = [3,3,6,5,-2,2,5,1,-9,4]
Output: true
Explanation: 3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4
 
Constraints:
3 <= A.length <= 50000
-10^4 <= A[i] <= 10^4
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/partition-array-into-three-parts-with-equal-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

三、My answer

class Solution:
    def canThreePartsEqualSum(self, A: List[int]) -> bool:
        if sum(A) % 3 != 0:
            return False
        target = sum(A) / 3
        if not A:
            return False
        sum_ = 0
        idx = 0
        for i in range(len(A)):
            sum_ += A[i]
            if i < len(A)-1:
                if sum_ == target:
                    idx = i
                    sum_ = 0
                    break
            else:
                return False
        for i in range(idx+1,len(A)):
            sum_ += A[i]
            if i < len(A)-1:
                if sum_ == target:
                    return True
            # 以下两个 return false 保留一个即可
            # else:
            #     return False
        return False

四、解题报告

只要找出三段,使每段数字之和等于总数组之和的三分之一即可。

一开始我将题目想复杂了,以为选出来的数字是打乱顺序的,费了好长时间重新审题之后才发现题目中已经说明 (A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1]) 。所以一定是按照原顺序划分。可以理解为将数组切两刀使每一部分加和相等,若能找出这两刀的位置则是True,否则 False。

相关文章
|
3月前
|
存储 Go 索引
go语言中的数组(Array)
go语言中的数组(Array)
127 67
|
5月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
63 0
|
7月前
|
算法
LeetCode第53题最大子数组和
LeetCode第53题"最大子数组和"的解题方法,利用动态规划思想,通过一次遍历数组,维护到当前元素为止的最大子数组和,有效避免了复杂度更高的暴力解法。
LeetCode第53题最大子数组和
|
5月前
|
人工智能 前端开发 JavaScript
拿下奇怪的前端报错(一):报错信息是一个看不懂的数字数组Buffer(475) [Uint8Array],让AI大模型帮忙解析
本文介绍了前端开发中遇到的奇怪报错问题,特别是当错误信息不明确时的处理方法。作者分享了自己通过还原代码、试错等方式解决问题的经验,并以一个Vue3+TypeScript项目的构建失败为例,详细解析了如何从错误信息中定位问题,最终通过解读错误信息中的ASCII码找到了具体的错误文件。文章强调了基础知识的重要性,并鼓励读者遇到类似问题时不要慌张,耐心分析。
105 5
|
5月前
|
存储 Java
Java“(array) <X> Not Initialized” (数组未初始化)错误解决
在Java中,遇到“(array) &lt;X&gt; Not Initialized”(数组未初始化)错误时,表示数组变量已被声明但尚未初始化。解决方法是在使用数组之前,通过指定数组的大小和类型来初始化数组,例如:`int[] arr = new int[5];` 或 `String[] strArr = new String[10];`。
138 2
|
5月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
39 4
|
5月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
42 0
Leetcode第三十三题(搜索旋转排序数组)
|
5月前
|
存储 JavaScript 前端开发
JavaScript Array(数组) 对象
JavaScript Array(数组) 对象
53 3
|
5月前
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
95 0
|
5月前
|
C++
【LeetCode 12】349.两个数组的交集
【LeetCode 12】349.两个数组的交集
35 0