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日

相关推荐

  • 剑指offer59-队列的最大值

    原题(来源Leetcode) 请定义一个队列并实现函数 max_value 得到队列里的最大值,要求函数max_value、push_back 和 pop_front 的时间复杂度…

    算法 2020年3月7日
    0130
  • 剑指offer46-把数字翻译成字符串

    原题 给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编…

    算法 2020年2月29日
    0300
  • leetcode658-找到K个最接近的元素

    原题 给定一个排序好的数组,两个整数 k 和 x,从数组中找到最靠近 x(两数之差最小)的 k 个数。返回的结果必须要是按升序排好的。如果有两个数与 x 的差值一样,优先选择数值较…

    算法 2020年1月4日
    0120
  • leetcode300-最长上升子序列

    原题 给定一个无序的整数数组,找到其中最长上升子序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,10…

    算法 2020年3月14日
    0250
  • leetcode101-对称二叉树

    原题 给定一个二叉树,检查它是否是镜像对称的。 例如,二叉树 [1,2,2,3,4,4,3] 是对称的。     1  &nbsp…

    算法 2020年1月11日
    0120
  • leetcode26-删除排序数组中的重复项

    原题 给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。 不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空…

    算法 2019年11月23日
    0190
  • leetcode167-两数之和II-输入有序数组

    原题 给定一个已按照 升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。 函数应该返回这两个下标值index1和index2,其中index1必须小于index2。 说明…

    算法 2019年11月20日
    0190
  • 海量数据-两种方法解决top k问题

    假如提供一百万个数据(甚至更大)的无序数组,如何从中获取最大的k个元素? 最容易想到的是先降序排序然后获取前k个元素,那假设我们用最常用的O(nlogn)级别的排序算法,要获取to…

    2020年4月4日
    0220
  • leetcode378-有序矩阵中第K小的元素

    原题 给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第k小的元素。请注意,它是排序后的第k小元素,而不是第k个元素。 示例: matrix = [ &nbs…

    算法 2020年2月14日
    0430
  • leetcode9-回文数

    原题 判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。 示例1: 输入: 121 输出: true 示例2: 输入: -121 输出: fa…

    算法 2020年2月28日
    0120

发表回复

登录后才能评论