arrays - 在排序数组中找到两个整数，使得 a - b = k

Question

给定一个整数 k和一个排序数组 A（可以由正数和负数组成），从 A 输出 2 个整数，使得a-b=kinO(n) time和O(1) space

O(n logn) 解决方案：

1. 遍历数组：O(n)
2. 对于 element 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)。有人知道吗？

Answer 1

制作两个索引指针 - 左和右，将两者都初始化为数组 (0) 的开头。如果 a[Left] + k > a[Right]，则向右递增，否则向左递增。相等时停止

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)空间。