2个数组中的等和子序列

Question

给定 2 个数组 A 和 B，select 来自 A 的子序列 X 和来自 B 的 Y，sum(X) 应等于 sum(Y)。我们必须找到我们可以select这种类型的子序列的方法的数量。

数组元素个数最多为100个数组中的值 -100 到 100

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

这是非常低效的，因为生成所有子序列的时间复杂度为 O(2^100)

有人可以帮我解决这个问题吗？我不需要代码，只要算法的想法就会很有帮助。

Answer 1

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

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

如果我们添加元素，总计数数组将移动元素的值。
如果我们不添加元素，sum count数组将保持不变。

// 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)

2个数组中的等和子序列

Equal sum subsequence in 2 arrays

algorithm

subsequence