leetcode1013-将数组分成和相等的三个部分

原题

给你一个整数数组 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. -10^4 <= A[i] <= 10^4

解法

思想

这道题的思想就是一个数组如果能分成三个和相等的部分,首先获取这个均分的值是多少,假设是x,然后从左往右第一个和为x的区间必须要算入,第二个和为x的区间也必须要算入,剩下的元素就必须是第三个区间,即和必须为x。

代码

class Solution {
    public boolean canThreePartsEqualSum(int[] A) {
        int sum = 0;
        for(int i:A) sum+=i;
        if(sum%3!=0) return false;
        int single = sum/3;
        int cur = 0;
        int count = 0;
        for(int i = 0;i<A.length;i++){
            cur+=A[i];
            if(cur==single && count!=2) {
                count+=1;
                if(count==2&&i==A.length-1) return false;
                cur = 0;
            }
        }
        return count==2 && cur==single;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode1013-%e5%b0%86%e6%95%b0%e7%bb%84%e5%88%86%e6%88%90%e5%92%8c%e7%9b%b8%e7%ad%89%e7%9a%84%e4%b8%89%e4%b8%aa%e9%83%a8%e5%88%86/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年3月11日 01:08
下一篇 2020年3月11日

相关推荐

  • 使用递归函数逆序一个栈

    原题(来源:牛客网) 一个栈依次压入1,2,3,4,5那么从栈顶到栈底分别为5,4,3,2,1。将这个栈转置后,从栈顶到栈底为1,2,3,4,5,也就是实现了栈中元素的逆序,请设计…

    算法 2020年4月19日
    0250
  • leetcode225--用队列实现栈

    原题 使用队列实现栈的下列操作: push(x) – 元素 x 入栈 pop() – 移除栈顶元素 top() – 获取栈顶元素 empty() – 返回栈是否为空 注意: 你只能…

    算法 2019年12月13日
    0100
  • leetcode99-恢复二叉搜索树

    原题 二叉搜索树中的两个节点被错误地交换。 请在不改变其结构的情况下,恢复这棵树。 示例 1: 输入: [1,3,null,null,2]    1 …

    算法 2020年3月1日
    070
  • leetcode15-三数之和

    原题 给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。 注意:…

    算法 2020年5月4日
    0180
  • leetcode232-用栈实现队列

    原题 使用栈实现队列的下列操作: push(x) – 将一个元素放入队列的尾部。 pop() – 从队列首部移除元素。 peek() – 返回队列首部的元素。 empty() – …

    算法 2019年12月13日
    0550
  • leetcode278-第一个错误的版本

    原题 你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。 假…

    算法 2020年1月2日
    080
  • leetcode263-丑数

    原题 编写一个程序判断给定的数是否为丑数。 丑数就是只包含质因数 2, 3, 5 的正整数。 示例1: 输入: 6 输出: true 解释: 6 = 2 × 3 示例2: 输入: …

    算法 2020年2月6日
    0100
  • leetcode983-最低票价

    原题 在一个火车旅行很受欢迎的国度,你提前一年计划了一些火车旅行。在接下来的一年里,你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。 火车…

    算法 2020年5月6日
    0120
  • leetcode36-有效的数独

    原题 判断一个 9x9 的数独是否有效。只需要根据以下规则,验证已经填入的数字是否有效即可。 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-…

    2019年12月26日
    090
  • leetcode350-两个数组的交集II

    原题 给定两个数组,编写一个函数来计算它们的交集。 输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2,2] 示例2: 输入: nums1 = …

    算法 2019年12月23日
    0390

发表回复

登录后才能评论