[LeetCode] 1354. 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，让我们从一个长度相同，但是全是1的数组开始变动，变化的规则是可以将任意位置上的数字变成当前数组的数字之和，并说了可以进行任意次数的变化，问最终是否能变化成给定的数组。参见题目中给定的例子不难理解题意，比如例子1中，就通过了三次变换，可以得到目标数组。而例子2，是没法得到的，因为初始数组的和为4，而目标数组中有个2，是小于4的。再比如例子3，题目中没有给变化过程，我们这里自己推导一下吧：

[1, 1] -> [1, 2] -> [3, 2] -> [3, 5] -> [8, 5]

博主最先看到这题的思路就是暴力搜索，从初始数组开始去尝试每一种可能，这种方法虽然可行，但是运算效率十分的低下，当数组的长度很大的时候，会无法通过 OJ，必须要想出更加优化的解法。由于这道题只是问能否组成目标数组，并不要求组成目标数组的不同方法，所以比较好的思路是倒着推，即从目标数组开始，往回推，看是否能得到初始数组。这种方法的优势在于，我们可以优先处理最大的数字，将其尽可能的最快减小到1。就拿题目中的例子1来举例吧，最大的数字是9，这个9怎么来的呢？在上一轮它是所有数字之和，这样话就可以通过减去其它所有数字得到替换之前的数字，即 9 - (5 + 3) = 1，说明是由 [1, 3, 5] 变化来的。接下来处理数字5，同样的方法求替换之前的数字 5 - (3 + 1) = 1，说明是由 [1, 3, 1] 变化来的。接下来处理数字3，同样的方法求替换之前的数字 3 - (1 + 1) = 1，说明是由 [1, 1, 1] 变化来的，这样就反推得到了初始数组。

这个是可以反推回去的情况，接下来想一下不能反推回去的情况，比如例子2中最大的数字是2，而其余数字之和是3，说明这个2并不是由数组之和变化来的，所以不能反推回去。这就是能反推的一个限定条件，即数组中最大的数字要大于其余数字之和，等于都不行，等于的话说明替换前的数字是0，是不对的，同理，最大数字是其余数字之和的整数倍也是不行的，因为最终还是会减到0。另一个限制条件就是其余数字之和也不能是0，因为初始数组每个数字都是1。说完了限制条件，再来说说到达什么条件就知道可以反推到初始数组，首先就是当数组中的最大数字为1的时候，因为此时在反推回去的过程中，上述的限制条件通过了之后，最大数字仍是1，说明所有数字都是1了，就满足条件了。其实还有个判断条件，即当其余数字之和为1的时候就可以返回 true，这个放到后面来解释。

先来解释一下代码，为了更好的取出最大数，这里用个优先队列，将目标数组所有数字放进去，就可以完成自动排序，同时计算出目标数组之和 sum。然后开始 while 循环，首先取出队首元素t，然后计算出其余数字之和，用数组数组总和 sum 减去t。此时需要判断下是否可以返回 true，即t是否等于1，或者其余数字之和 sum 是否等于1（后面讲解）。不能直接返回 true 的话，就来检查上面解释过的限制条件，即若t小于 sum，或者 sum 等于0，或者t是 sum 的整数倍时，都要返回 false。此时t要对 sum 取余，为啥不是相减，而是取余呢，这其实是一种优化，若数组中最大数字远大于其他数字之和，则减过一次之后还有可能大于其余数字之和，这时为了避免大量的重复计算，则可以直接用取余来跳过重复的步骤。

好，现在再来解释一下前面为啥判断 sum 为1的时候，就可以返回 true。因为这种情况只有一种可能，就是数组中只有两个数字，当前数字是2，而另一个数字是1，这种情况下之所以没法通过下一轮遍历中判断最大数字是1来返回 true，是由于任何数字对1取余都会变成0，于是只能通过判断 sum 的值来返回 true 了，这也是用取余操作比较 tricky 的地方。得到新的 t 之后，要将其加到 sum 中，此时的 sum 就是当前数组所有数字之和了，就可以在下一轮循环中，再减去最大数字，从而又可以得到其它数字之和的那个 sum 了，参见代码如下：

class Solution {
public:
    bool isPossible(vector<int>& target) {
        long sum = 0;
        priority_queue<int> pq;
        for (int num : target) {
            pq.push(num);
            sum += num;
        }
        while (true) {
            int t = pq.top(); pq.pop();
            sum -= t;
            if (t == 1 || sum == 1) return true;
            if (t < sum || sum == 0 || t % sum == 0) return false;
            t %= sum;
            sum += t;
            pq.push(t);
        }
        return true;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1354

类似题目：

Minimum Amount of Time to Fill Cups

参考资料：

https://leetcode.com/problems/construct-target-array-with-multiple-sums/

https://leetcode.com/problems/construct-target-array-with-multiple-sums/solutions/510256/java-c-python-backtrack-oj-is-wrong/

https://leetcode.com/problems/construct-target-array-with-multiple-sums/solutions/2189445/visual-explanation-java-max-heap/

LeetCode All in One 题目讲解汇总(持续更新中...)