2个数组中的等和子序列

Question

给定两个数组A和B，从A中选择一个子序列X，从B中选择Y，求和（X）应等于求和（Y）。我们必须找到选择这类子序列的方法。

数组中的元素数最多可以是100个值-100到100

我的方法是：生成两个数组的所有子序列，取它们的和，对于每个可能的和，将我们在数组A中找到的子序列的否与我们在数组B中找到的具有该和的子序列的否相乘。

这是非常低效的，因为生成的所有子序列都是O（2^100）

有人能帮我吗？我不需要代码，只是algo的想法会非常有用。

Answer 1

请注意，sum（X）或sum（Y）的范围是从-10000到10000
因此，如果将所有值存储在长度为20001的数组中，我们可以跟踪所有值。我们可以循环其中一个数组中的每个元素，跟踪sum count数组，并重复另一个数组。

对于每个元素，我们要么将元素添加到和中，要么不将元素添加到和中。

1. 如果我们添加元素，sum count数组将按元素的值移位
2. 如果不添加元素，总和计数数组将保持不变

// let the sum count array be named num and has length 20001 (all filled with 0)
vector<int> num(20001, 0);
// the following line set count of sum = 0 to 1 (position 10001(one based) in the array, As I shift all value by 10000 to handle negative sums)
num[10000] = 1;
for (int i = 0; i < 100; ++i) {
    vector<int> num2(num); // copy num to num2 (Done (2.))
    for (int j = 0; j < 20001; ++j) {
        if (j + A[i] >= 0 && j + A[i] < 20001)
            // Add (1.)
            num2[j + A[i]] += num[j];
    }
    // c++ optimization, we just want num to become num2 and we can destroy num2
    num = num2.move(); 
}

如果我们从（1）中求和数组和（2.），它将是新的和计数数组，为插入下一个元素做好准备。每个元素的复杂度为O（20001）
生成和计数数组的总体复杂度约为O（2*20001*100）<附加O（20001）以获得最终答案<所以总体复杂度是O（2*20001*100 20001）