在一个排序数组中找到两个整数，使得它们的差等于k。

Question

给定一个整数k和一个排序数组A（可以包含正数和负数），输出A中的2个整数，使得a-b=k，并且时间复杂度为O(n)，空间复杂度为O(1)。

O(n logn)解决方案：

1.遍历数组：O(n)

2.对于元素a[i]，使用二分查找在数组中找到a[i]+k：O(log n)

总时间：O(n logn)

O(n)解决方案：

1.将数组的所有元素存储在哈希表中：O(n)

2.对于元素a[i]，检查哈希表中是否存在a[i]+k：O(1)

总时间：O(n)

空间：O(n)

但是他想要一个O(n)解决方案，并且额外空间复杂度为O(1)。有人有什么想法吗？

- Ravi Gupta

---

“ve”和“nos”是什么意思？ - ninjagecko

@ninjagecko 这是“positive”（+ve）和“negative”（-ve）的简写。 - RJ Lohan

搜索时间还是存储时间？在一边构建一个二叉树，其中<k的元素在一侧，>k的元素在另一侧。 <a>必须>=<k>。对于树的一侧的每个项目，在另一侧进行二分搜索。好吧，这是我能做到的最好的：O - starbolin

Answer 1

创建两个索引指针 - 左和右，将它们都初始化为数组的开始（0）。如果 a[Left] + k > a[Right]，则增加 Right，否则增加 Left。当它们相等时停止。

- MBo

---

你最初将Left和Right分配给哪个索引？根据它们的名称，我假设分别为0和N-1。如果是这样，增加Right将使其指向数组越界的索引。 - Ravi Gupta

@Ravi Gupta 我只是试图给出思路，而不是解决方案。同时增加两个的假设是在开始时 Right 不能在结尾。 - MBo

Answer 2

这个想法是使用两个指针指向数组，称为a和b。 最初它们都指向开头(a=b=0)。

如果ar[a]+k < ar[b]，那么你就移动a。

如果ar[a]+k > ar[b]，那么你就移动b。

如果ar[a]+k == ar[b]，那么你已经找到了一个解决方案。

这样做的时间复杂度为O(n)，空间复杂度为O(1)。

- Petar Ivanov

---

原帖中给出的方程式为 a - b = k，在您的符号表示中，应该是 ar[a] - ar[b] = k。如果您交换索引 a 和 b（例如，“如果 ar[b] + k < ar[a]，则将 a 增加1”），那么您的解决方案就可以奏效了。另外，为了保持符号表示与原问题一致，我建议使用 i 代替第一个索引 a，使用 j 代替第二个索引 b，使用 A 代替 ar。然后，解决方案就是 a = A[i] 和 b = A[j]，并且您需要返回 a 和 b。 - gotgenes

“如果 ar[b] + k < ar[a]，那么你前进 a”是错误的。尝试一下就会发现。虽然变量的命名方式并不重要，但我同意有些选择比其他选择更好 :) - Petar Ivanov