algorithm - 在数组中查找满足 a%b = k 的对，其中 k 是给定的整数

Question

这是我遇到的一个有趣的编程难题。给定一个正整数数组和一个数字 K。我们需要从该数组中找到满足 a % b = K 的 pairs(a,b)。

我有一个天真的 O(n^2) 解决方案，我们可以在其中检查所有对，使得 a%b=k。有效但效率低下。我们当然可以做得更好，不是吗？有什么有效的算法吗？哦，这不是家庭作业。

Answer 1

对数组进行排序和二进制搜索，或者保留一个哈希表，其中包含数组中每个值的计数。

对于一个数 x，我们可以找到最大的 y 使得 x mod y = K as y = x - K。二进制搜索此 y 或在您的哈希中查找它并相应地增加您的计数。

现在，这不一定是唯一有效的值。例如，8 mod 6 = 8 mod 3 = 2。我们有:

x mod y = K => x = q*y + K =>
            => x = q(x - K) + K =>
            => x = 1(x - K) + K =>
            => x = 2(x - K)/2 + K =>
            => ...

这意味着您还必须测试 y 的所有约数。您可以在 O(sqrt y) 中找到除数，如果使用二进制搜索和 ，则总复杂度为 O(n log n sqrt(max_value)) O(n sqrt(max_value)) 带有哈希表(特别推荐，如果你的数字不是很大)。