查找列表中的数字在添加或减去时是否等于 a mod b 的算法

Question

当我遇到一个有趣的问题时，我正在做一些面试问题，但我想不出解决方案。问题状态:

Design a function that takes in an array of integers. The last two numbers in this array are 'a' and 'b'. The function should find if all of the numbers in the array, when summed/subtracted in some fashion, are equal to a mod b, except the last two numbers a and b.

例如，假设我们有一个数组:

array = [5, 4, 3, 3, 1, 3, 5].

我需要查明此数组中是否存在 +/- 的任何可能“位置”，以便数字可以等于 3 mod 5。该函数应为此数组打印 True，因为 5+4-3+3-1 = 8 = 3 mod 5。

“显而易见”且简单的解决方案是尝试以所有可能的方式添加/减去所有内容，但这是一个非常耗时的解决方案，也许 O(2ⁿ)。

有什么更好的办法吗？

编辑:问题要求函数使用数组中的所有 数字，而不是任何。当然，最后两个除外。

Answer 1

如果有n个数，那么有一个简单的算法在O(b * n)中运行:对于k = 2到n，计算整数集合x使得前k个数的和或差为等于 x 模 b。

对于 k = 2，该集合包含 (a_0 + a_1) 模 b 和 (a_0 - a_1) 模 b。对于 k = 3, 4, ..., n ，您取前一组中的数字，然后加上或减去数组中的下一个数字。最后检查 a 是否是最后一组的元素。