arrays - 如何从两个数组中选择元素，使它们的总和最小？

Question

我有两个等长的数组，里面填满了整数(可以是正数也可以是负数，但绝不能为 0)。在每个索引处，我可以选择 array1 或 array2 中的元素，并且这些元素之和的绝对值应该是最小值。

例如:

a1 = [2, 2, 1]
a2 = [-3, -3, -4]

正确的答案应该是这样选择:

At index 0 : -3 from a2
At index 1 : 2 from a1
At index 2 : 1 from a1

因此，最终总和将为 0。

Answer 1

首先，简化问题:

• 创建数组b，其中b[i] = a1[i] - a2[i]。
• sumA1 = a1 中每个元素的总和。

那么问题就变成了:

Find a sub array from b, mark as c, mark its sum as sumC which should be closest to sumA1.

Or, you can also say it should have minimal Math.abs(sumC - sumA1).

BTW, if c is empty, it's also valid, which means choose all indices from a1.

那么这个问题类似于这个问题:Given an input array find all subarrays with given sum K

或者，引用这篇文章:

• Subarray whose sum is closest to K
• Find subarray with given sum | Set 2 (Handles Negative Numbers)

然后，回到 OP 的问题:

• 在 b 中选取的任何索引都用于 a2。
• b 中未选取的任何索引均用于 a1。