java - 如何以独特的方式分配变量以求减法中的补数

Question

我试图分配变量“complement”，使得表达式 Math.abs(array[i]-complement)==diff 为真，但我很困惑如何实现它。我考虑过尝试使用条件语句，在 array[i] 大于 diff 的情况下，那么 complement 会发生什么，但是这些条件并不总是在所有情况下都为真。有人可以告诉我这是否可能吗？如果不可能，我该怎么办？

本质上，我试图找出数组中存在多少种方式，其中它们的差异等于某个数字(变量diff)，并且我想找到“补数”，所以我可以快速在哈希表中查找 O(N) 时间复杂度。

Answer 1

这基本上就是2-diff问题。

我可以写出伪代码，但实现取决于你!

前言

您的代码应该在 O(n) 内运行，这样您就可以了解如何实现此解决方案。 O(n) 建议您逐一循环数字，并且不应该有任何嵌套循环!

您还希望使用 HashMap 来快速循环值。 我们使用 hashmap 来存储每个数字的补数，以便以后遇到它们!

伪代码

let nums be our array of numbers
let diff be our difference
let hash be a hashtable under SUHA

for each num in nums:
    if (num in hash):
        (num, hash[num]) is our pair!
    let c1 = num + diff
    let c2 = num - diff

    hash[c1] = num
    hash[c2] = num

就是这样!

直觉

HashMap 存储了数字的所有补数，因此当我们查看 HashMap 时，我们基本上会问:“这个数字是我们已经见过的另一个数字的补数吗？”