【LeetCode】1020. Partition Array Into Three Parts With Equal Sum 解题报告(Python)
作者: 负雪明烛
id: fuxuemingzhu
个人博客: http://fuxuemingzhu.cn/
题目地址: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:
- 3 <= A.length <= 50000
- -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
参考资料:https://leetcode.com/problems/partition-array-into-three-parts-with-equal-sum/discuss/260885/C%2B%2B-6-lines-O(n)-target-sum
日期
2019 年 3 月 24 日 —— 这个周赛太悲催了
最新文章
- 合理利用gradle的占位符功能
- Java反射的一些理解
- php部分---注册审核
- fdisk命令使用说明
- Wifi开发技术总结1
- BST &; Treap
- hdu 3117 Fibonacci Numbers
- Card Collector(HDU 4336)
- Python标准库---子进程 (subprocess包)
- Bellman 算法
- Js版游戏打砖块开发过程详细
- Pro Aspnet MVC 4读书笔记(3) - Essential Language Features
- ConcurrentHashMap原理
- C# MVC权限验证
- C# 添加、修改和删除PDF书签
- spark 机器学习基础 数据类型
- linux下查找堆栈信息例子
- CCS中cmd文件的编写
- 从本地新建项目到提交到github
- gitlab修改默认端口
热门文章
- 【shell】循环将字符串写入数组中?
- Oracle-with c as (select ......) 实现多次调用子查询结果
- Kubernetes-存储(一)
- 网口程序udp
- git pull、git fetch、git merge、git rebase的区别
- Linux环境下为普通用户添加sudo权限
- redis入门到精通系列(九):redis哨兵模式详解
- Linux:while read line与for循环的区别
- 基于阿里云ecs(centos 7) 安装jenkins
- ES6——>;let,箭头函数,this指向小记