原文链接: https://leetcode-cn.com/problems/construct-target-array-with-multiple-sums

英文原文

You are given an array target of n integers. From a starting array arr consisting of n 1's, you may perform the following procedure :

• let x be the sum of all elements currently in your array.
• choose index i, such that 0 <= i < n and set the value of arr at index i to x.
• You may repeat this procedure as many times as needed.

Return true if it is possible to construct the target array from arr, otherwise, return false.

 

Example 1:

Input: target = [9,3,5]
Output: true
Explanation: Start with arr = [1, 1, 1] 
[1, 1, 1], sum = 3 choose index 1
[1, 3, 1], sum = 5 choose index 2
[1, 3, 5], sum = 9 choose index 0
[9, 3, 5] Done

Example 2:

Input: target = [1,1,1,2]
Output: false
Explanation: Impossible to create target array from [1,1,1,1].

Example 3:

Input: target = [8,5]
Output: true

 

Constraints:

• n == target.length
• 1 <= n <= 5 * 104
• 1 <= target[i] <= 109

中文题目

给你一个整数数组 target 。一开始，你有一个数组 A ，它的所有元素均为 1 ，你可以执行以下操作：

• 令 x 为你数组里所有元素的和
• 选择满足 0 <= i < target.size 的任意下标 i ，并让 A 数组里下标为 i 处的值为 x 。
• 你可以重复该过程任意次

如果能从 A 开始构造出目标数组 target ，请你返回 True ，否则返回 False 。

 

示例 1：

输入：target = [9,3,5]
输出：true
解释：从 [1, 1, 1] 开始
[1, 1, 1], 和为 3 ，选择下标 1
[1, 3, 1], 和为 5， 选择下标 2
[1, 3, 5], 和为 9， 选择下标 0
[9, 3, 5] 完成

示例 2：

输入：target = [1,1,1,2]
输出：false
解释：不可能从 [1,1,1,1] 出发构造目标数组。

示例 3：

输入：target = [8,5]
输出：true

 

提示：

• N == target.length
• 1 <= target.length <= 5 * 10^4
• 1 <= target[i] <= 10^9

通过代码

高赞题解

二哥牛逼，一楼孝敬二哥，比赛时参考了二哥的方法，但是有很多不足，下面这个是直接推的思路：

        关键是我们要倒推当前数组中最大元素的位置上它的上一个值是多少，比如 $[5,8]$，当前最大是 $8$，$cur=8$ ,$rest = sum(为13)-8=5$，计算$8$的这个位置之前是几: $pre=8-5=3$，这样我们就得到 $8$ 之前位置上的数字是 $3$ 了，同样的原理，倒推，模拟一下：$[5,8]==>[5,3]==>[2,3]==>[2,1]==>[1,1]$

能过是力扣数据弱，碰到 $[1000000000, 1]$ 这样的用例，就过不去了。推荐二哥的题解！。

public boolean isPossible(int[] target) {
    PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
    int sum = 0;
    for (int i = 0; i < target.length; i++) {
        pq.add(target[i]);
        sum += target[i];
    }

    while (sum != target.length) {
        int cur = pq.poll();
        int rest = sum - cur;
        int pre = cur - rest;
        if (pre >= cur || pre < 1) {    //关于这里为什么要两个判断，请见评论区。还是小伙伴们厉害
            return false;
        }
        sum = cur;
        pq.offer(pre);
    }
    return true;
}

二哥的题解@scut_dell，我只是搬运！大家参考讨论区即可

public boolean isPossible(int[] target) {
    if (target.length == 1) {
        return true;
    }
    PriorityQueue<Long> pq = new PriorityQueue<>(Collections.reverseOrder());
    long sum = 0;
    for (int i = 0; i < target.length; i++) {
        sum += target[i];
        pq.offer((long)target[i]);
    }
    //如果此时队列为空或者最大值就是1，直接return true
    if (pq.isEmpty() || pq.peek() == 1) {
        return true;
    }
    while (true) {
        //取出最大的那个
        Long poll = pq.poll();
        //如果此时堆中最大的为1
        if (pq.peek() == 1) {
            //直接看它满足或不满足公式
            return (poll - 1) % (sum - poll) == 0;
        } else {
            //需要计算多少轮才能比第二小的数小
            long n = (poll - pq.peek()) / (sum - poll) + 1;
            //得到这个数字
            long x = poll - n * (sum - poll);
            if (x <= 0) {
                return false;
            }
            //更新sum
            sum = poll - (sum - poll) * (n - 1);
            pq.offer(x);
        }
    }
}

统计信息

通过次数	提交次数	AC比率
2975	10597	28.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言