寻找所有满足两数之和小于S的数字对。

Question

给定一个有序数组 a[0...n-1]，找到所有其两数之和小于 S 的数字对。 是否存在 O(n) 解法？

- shreyasva

---

考虑到你只是在严格处理数字对，是的。 - Jerry Coffin

你有三个点 ...，同时从 n 中减去了 1。你确定两者都需要吗？nos 是什么？ - sawa

Jerry：但是在列表中有O(n^2)对。 - Gabe

Answer 1

您现在正在面试吗？他们很快会回到房间吗？

既然已经排序，那么解决方案之一（如果有的话！）就是[0]和一些最高的[M]。然后从0开始向上移动较低的索引，从M向下移动较高的索引。还有一些关于何时推出哪些内容的详细信息。

编辑--由于仍然可能存在O(n^2)的解决方案（例如，如果S比最大条目的两倍还要大），一个技巧是将解决方案表达为范围。否则，仅枚举将需要太长时间。

- david van brink

---

问题中没有提到M，但是假设它是n-1，那么"其中一个解（如果有的话！）是[0]和[M]"这个说法是错误的。最可能的解是[0]和[1]，可以很容易地在范围内，而[0]和[M]则大于等于S。范围是一个好主意。 - Tony Delroy

Answer 2

这可能会有所帮助：

在数组中找到两个数字，使它们的和等于X

- zengr

Answer 3

David的解决方案应该是可行的。即使有超过N个解决方案，它也将是O(N)。

1）从*ptr1 = a [0]和*ptr2 = a [X] <= S（X不总是N-1）开始

2）向后移动ptr2，直到ptr1 + ptr2 <= S。

--此时，ptr1 +所有指针到ptr2的索引都是解决方案。

3）将ptr2向后移动一个索引，并将ptr1向上移动一个索引

--重复

直到ptr1> ptr2

- Jess

Answer 4

枚举所有这样的对已经是O(n^2)（注意，这与精确求和到S的问题不同，因为在那种情况下，枚举可以像“3次对（w，x），1次对（y，z）...”一样在O(n)内完成）

- dcn

Answer 5

没有O(n)的解决方案。例如，如果您有像这样的列表：1,2,3,4...n和S=3*n，那么每对数字的总和都小于S。而需要返回的配对数是n*(n-1)/2。

- Andras