LEETCODE 1354. Construct Target Array With Multiple Sums 解题思路分析

题目大意：

多次求和构造目标数组

给你一个整数数组 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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1354

解题思路分析：

本题要求是否能够将一个全是1的数组，经过一系列变化变成给定数组target，变化的方式是将当前数组的数字和赋值到数组的任意一位置上。如果我们正向思考的话，每次需要考虑n种情况，n为数组长度，即尝试将数组的和赋值到数组的每一位，查看最终是否能够出现目标数组。但是如果反过来思考，我们利用target数组来反推全是1的数组就会相对简单许多，target数组中最大值max一定是最后一步变化得来的，这个max变化前的前身是max减去剩余数字的和。计算出max的前身之后，我们利用它的前身替换掉数组中的max值，再重复上述步骤。

在反推过程中，因为所有数字都是大于等于1的，所以当遇到最大值max小于剩余数字和的情况时，说明max的前身只能是负数，这不符合题意，可以返回false。如果最大值max等于剩余数字和，说明max的前身是0，同样不符合题意，除非max是1，即当数组中最大值等于1时，说明数组中所有数组都已经变成1，返回true。

我们举个例子，比如[5,8]。此时max是8，8的前身是8减去数组中其他数字和5，为3，将8的前身替换掉8，数组变为 [5,3]，此时max是5，5的前身是5-3=2。数组变成 [2,3]。接下来同理，数组继续变化成 [2,1]，最后变为 [1,1]。

以上即是本题的核心解题思路。不过提交代码后发现一个极端测试用例，[1,1000000000]，此时max是1000000000，它的前身是999999999，仍然是最大值，这样我们需要进行999999999次减一计算才能将target数组变成 [1,1]。这时我们可以直接使用求余运算，余数即是max前身。另外如本例，当余数为0时（1000000000%1），说明max的前身与其他数字之和相同，上文我们说过，如果一个数字与其他数字和相同时，需要看max是否为1，如果是1，返回true，否则返回false。

解题时，我们可以使用PriorityQueue来保存数组中的数字，这样我们可以快速的取出数组中的最大值max。另外我们需要提前计算出数组中所有数字和sum。变化过程中将max以外数字和可以通过sum-max计算得出。将max变成其前身后，注意别忘了将sum减去max与前身的差值。

其实本题与我们之前讲过的一道题目非常类似：

LEETCODE 780. Reaching Points 解题思路分析

780. Reaching Points那道题比本题略微简单，它只是一个长度为2的数组，而本题数组长度不定，最大可能是5万。

实现代码：

public boolean isPossible(int[] target) {
    // 定义PriorityQueue，排序为由大到小
    PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->b-a);
    // 数组元素和
    long sum=0;
    // 循环每一个元素
    for(int num: target){
        sum+=num; // 累加数组元素和
        q.offer(num); // 将当前元素添加到Queue
    }
    // 当数组元素和大于数组长度时循环
    // 当sum等于数组长度时，说明元素值都是1
    while(sum>target.length){
        int max=q.poll(); // 取出最大值
        long rest=sum-max; // 数组中剩余元素和
        // 如果最大值小于等于剩余元素和，返回false
        if(max<=rest) return false;
        // 计算max的前身
        int pre = (int)(max % rest);
        // 如果前身是0时(max与rest余数为0)。
        // 说明max的前身与剩余数字和相同。
        // 如果剩余数字和是为1，说明前身也是1，返回true
        if(pre==0) return rest==1;
        // 更新所有数字和
        sum-=(max-pre);
        // 将前身加入到Queue
        q.offer(pre);
    }
    return true;
}

本题解法执行时间为7ms。

Runtime: 7 ms, faster than 72.91% of Java online submissions for Construct Target Array With Multiple Sums.

Memory Usage: 48.2 MB, less than 100.00% of Java online submissions for Construct Target Array With Multiple Sums.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1354-construct-target-array-with-multiple-sums-解题思路分析/