在已排序的数组中查找一对整数，使它们的和为K。

Question

给定一个排序好的整数数组，如何找到一对整数使它们的和为K？

例如，数组array = 1,3,5,6,10，K = 6，答案是1和5。

时间复杂度应该尽量小。

- akshay

---

听起来很像今天流传的这篇博客文章：http://www.codingatwork.com/2011/07/array-sum/ - evan

你的大学学术政策和教授的政策是否允许你在互联网上询问他人来回答你的作业问题？ - Dan Grossman

这个问题以前已经被问过无数次了，甚至在这里也是如此。在发帖之前，请至少进行一次谷歌搜索。至于解决方案，为了最小化时间使用哈希表。为了最小化空间，请对数组进行排序，有两个指针分别指向两端，并根据需要递增和递减它们。 - Kakira

你说你有一个已排序的数组。但是示例数组并没有排序。那到底是哪个？ - svick

Answer 1

您可能想看一下这篇博客文章：http://www.codingatwork.com/2011/07/array-sum/ 我的方法是在列表中进行二分查找，查找K/2，然后移动一个变量a到左边，另一个变量b到右边，尝试找到一个解a+b=K。

我的想法是从小于或等于K/2的最大数字开始a，从大于a的最小数字开始b。再次使用二分查找来查找a，并让b成为数组中的下一个元素。然后：

• 如果a+b = K，则返回(a,b)。
• 如果a+b < K，则将b向右移动一个位置。
• 如果a+b > K，则将a向左移动一个位置。

当然，您可以跳过二分搜索，直接从数组开头开始a，从数组末尾开始b，然后执行以下操作：

• 如果a+b = K，则返回(a,b)。
• 如果a+b < K，则将a向右移动一个位置。
• 如果a+b > K，则将b向左移动一个位置。

这可能更快。

- PengOne

Answer 2

有一个线性（O(n)）的解决方案。

使用哈希表，在遍历数组时检查当前元素是否已经在哈希表中存在 - 如果是，则已经找到答案。否则，插入等于K减去当前元素的数字。顺便说一下，这适用于非排序数组。

int[] ar = new int[] { 1, 4, 3, 5 };
int K = 6;

HashSet<int> set = new HashSet<int>();
foreach (int a in ar)
{
    if (set.Contains(a))
    {
        Console.WriteLine(a + ", " + (K - a));
        break;
    }

    set.Add(K - a);
}

- Petar Ivanov

Answer 3

function findpairzero(arr) {
 let left = 0;
 let right = arr.length - 1;

 while (left < right) {
 if (arr[left] + arr[right] === 0) {
  return [arr[left], arr[right]];
  } else if (arr[left] + arr[right] > 0) {
  right--;
  } else {
  left++;
 }
}
}

console.log(findpairzero([-4, -3, -2, -1, 0, 3, 2, 4, 5]));

- Mukul Reksh