给定一个整数k和一个排序数组A(可以由正数和负数组成)，从A中输出2个整数这样a-b=k O(n) 时间 和 O(1) 空间
O(n logn) 解:
- 遍历数组:
O(n) - 对于元素
a[i]，使用二进制搜索在数组中找到a[i]+k:O(log n)
总时间:O(n logn)
O(n) 解:
- 将数组的所有元素存储在一个哈希表中:
O(n) - 对于元素 a[i]，检查哈希表中的 a[i]+k 是否为:
O(1)
总时间:O(n)
空间:O(n)
但他想要一个具有 O(1) 额外空间的 O(n) 解决方案。有人知道吗？
最佳答案
制作两个索引指针 - 左和右，将两者初始化为数组 (0) 的开头。如果 a[Left] + k > a[Right]，增加 Right，否则增加 Left。相等时停止
关于arrays - 在排序数组中找到两个整数，使得 a - b = k，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10908663/