在排序数组中找到两个整数，例如a-b=k。-Findtwointegersinasortedarraysuchthata-b=k

Given an integer k and an sorted array A (can consist of both positive and negative numbers), output 2 integers from A such that a-b=k in O(n) time and O(1) space

给定一个整数k和一个已排序的数组A(可以包含正数和负数)，从A中输出两个整数A -b=k (n)时间和O(1)空间。

O(n logn) Solution:

O(n logn)解决方案:

1. Traverse the array: O(n)
2. 遍历该数组:O(n)
3. For element a[i], find a[i]+k in the array using binary search :O(log n)
4. 对于元素a[i]，使用二进制搜索在数组中找到[i]+k:O(log n)

Total Time: O(n logn)

总时间:O(n logn)

O(n) Solution:

O(n)解决方案:

1. Store all elements of the array in a Hash Table: O(n)
2. 将数组中的所有元素存储在散列表中:O(n)
3. For element a[i], check whether a[i]+k in the hash table : O(1)
4. 对于元素a[i]，检查哈希表中的[i]+k: O(1)

Total Time: O(n)

总时间:O(n)

Space: O(n)

空间:O(n)

But he wants an O(n) solution with O(1) extraspace. Anyone have any idea?

但是他想要一个O(n)的解。有人知道吗?

2 个解决方案

#2

---

8  

Make two index pointers - Left and Right, initialize both to the start of array (0). If a[Left] + k > a[Right], increment Right, else increment Left. Stop when equal

创建两个索引指针——左和右，初始化到数组的开始(0)。如果一个(左)+ k > a[右]，增量右，其他增量左。当相等