1013. Partition Array Into Three Parts With Equal Sum

2023-12-21 15:59

本文主要是介绍1013. Partition Array Into Three Parts With Equal Sum,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

 

提示:

  1. 3 <= A.length <= 50000
  2. -10000 <= A[i] <= 10000

解法一

//时间复杂度O(n), 空间复杂度O(n)
class Solution {
public:bool canThreePartsEqualSum(vector<int>& A) {int n = A.size();vector<int> vec(n);vec[0] = A[0];for(int i = 1; i < n; i++) {vec[i] += vec[i - 1] + A[i];//前i项累积和}if(vec[n - 1] % 3 != 0) return false;int i = 0, pts = vec[n - 1] / 3;//部分和while(i < n && vec[i] != pts) i++;if(i == n) return false;while(i < n && vec[i] != 2 * pts) i++;return i < n - 1;}
};

解法二

//时间复杂度O(n), 空间复杂度O(1)
class Solution {
public:bool canThreePartsEqualSum(vector<int>& A) {int average = 0, psum = 0, count = 0;for(int num : A) average += num;if(average % 3 != 0) return false;average /= 3;for(int num : A) {psum += num;if(psum == average) {count++;psum = 0;} }return count == 3;}
};

解法一:

对数组的第i项,记录其前i项的累积和vec[i]。

  1. 如果其总和vec[n - 1]不是3的倍数,则一定不能分成相等的三份,直接返回false;
  2. 如果是3的倍数,其应该有3个子数组,部分和为pts = vec[n-1]/3。遍历累积和,找出其中是否同时存在pts和2 * pts。若有则返回true,否则为false。

解法二:

思路类似,对解法一的空间效率加以优化。

2019/09/03 13:55

这篇关于1013. Partition Array Into Three Parts With Equal Sum的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/520606

相关文章

最大流=最小割=最小点权覆盖集=sum-最大点权独立集

二分图最小点覆盖和最大独立集都可以转化为最大匹配求解。 在这个基础上,把每个点赋予一个非负的权值,这两个问题就转化为:二分图最小点权覆盖和二分图最大点权独立集。   二分图最小点权覆盖     从x或者y集合中选取一些点,使这些点覆盖所有的边,并且选出来的点的权值尽可能小。 建模:     原二分图中的边(u,v)替换为容量为INF的有向边(u,v),设立源点s和汇点t

如何导入sun.misc.BASE64Encoder和sum.misc.BASE64Decoder

右击项目名--->Build Path--->Configure Build Path...--->java Build Path--->Access rules:1 rule defined,added to all librar...   --->Edit --->Add...

Three 渲染器(二)

WebGL1Renderer 构造函数 WebGL1Renderer( parameters : Object ) Creates a new WebGL1Renderer. 属性 See the base WebGLRenderer class for common properties. 方法 See the base WebGLRenderer class for common

【uva】11536-Smallest Sub-Array(区间移动问题)

一个区间移动的问题,1A了,感觉没什么好说的。。 13975926 11536 Smallest Sub-Array Accepted C++ 0.809 2014-08-01 11:00:20 #include<cstdio>#include<cstring>#include<iostream>using namespace std;#define INF 1 << 30

leetcode#628. Maximum Product of Three Numbers

题目 Given an integer array, find three numbers whose product is maximum and output the maximum product. Example 1: Input: [1,2,3]Output: 6 Example 2: Input: [1,2,3,4]Output: 24 Note: The lengt

leetCode#448. Find All Numbers Disappeared in an Array

Description Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements of [1, n] inclusive that do not appear in this

18. 4 Sum

题目: 解答: 与之前的三数之和的解法类似,也是先排序,然后不断剔除不可能的条件,最后两个参数,通过两头求和计算得出。 代码: class Solution {public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> result;int len = nums.size

apt-get update更新源时,出现“Hash Sum mismatch”问题

转载自:apt-get update更新源时,出现“Hash Sum mismatch”问题 当使用apt-get update更新源时,出现下面“Hash Sum mismatch”的报错,具体如下: root@localhost:~# apt-get update ...... ...... W: Failed to fetch http://us.archive.ubuntu.com/ub

做一个问卷考试,标准答案对比用户填写的答案,array_diff 进行差集比对

if( empty(array_diff($answer_mark, $answer)) && empty(array_diff( $answer,$answer_mark))){//用户答题正确}else{// 答题错误} 做一个问卷考试,标准答案对比用户填写的答案,array_diff  进行差集比对   如用户填写的答案变量为answer   标准答案为answer_mark

翻译HoudiniEngine官方文档:Parts

官方文档:《Houdini Engine 3.6: Parts》 介绍 Part 包含了你实际感兴趣的 mesh、几何体、attribute 数据。 Part 的划分基于几何体 primitive 的 group 。每一个 primitive group 对应一个 Part,如果有不属于任何 group 的几何体则他们将算作一个新的 Part。如果在一个 primitive group 有多