如何在O(n)时间复杂度内，在已排序的数组中找到两个数使它们的和等于给定的数字？

Question

public static void findNumber(int number) {
    int[] soretedArray = { 1, 5, 6, 8, 9 };
    for (int i = 0; i <= soretedArray.length; i++) {
        for (int j = i + 1; j < soretedArray.length; j++) {
            if (soretedArray[i] + soretedArray[j] == number) {
                System.out.println(soretedArray[i] + "::" + soretedArray[j]);
                return;
            }
        }
    }
}

使用这段代码，我能够找到数字，但时间复杂度是O(N^2)。我需要使用O(N)的时间复杂度，即在Java中只使用一个for循环或哈希映射或类似的方法来完成。

- Maklee Lee

---

https://tp-iiita.quora.com/The-Two-Pointer-Algorithm - xrisk

从你的代码中我理解到，如果有多个解决方案，你只需要找到其中一个是吗？ - Ole V.V.

Answer 1

我记得我曾经观看过Google官方视频讲解这个问题。虽然视频中没有用Java演示，但是通过不同变体的步骤进行了详细的解释。你一定要去看一下：如何在Google工作——编码/工程面试示例。

- Aleksandar G

---

彻底解释了答案，视频长度为24分钟。正如Rishav在评论中所说，它使用两个（指针）数组索引。它的运行时间复杂度确实是O(n)。 - Ole V.V.

Answer 2

如 Alexander G 提供的Google视频 所解释的那样，使用两个数组索引。将其中一个初始化为第一个元素（0），另一个初始化为最后一个元素（sortedArray.length-1）。在循环中，检查这两个索引处的两个元素的和。如果和是你要找的数字，你就完成了。如果���太高，你需要在其中一个索引处找到一个更小的数字; 将右侧索引向左移动一步（因为数组已排序，这是正确的方法）。另一方面，如果所得到的和太低，则将左侧索引向右移动以获得更高的第一个加数。当两个索引相遇时，如果你仍然没有找到你要找的总和，那么就没有了。此时，你已经通过了循环 n - 1 次，因此该算法的运行时间为 O(n)。

我们首先应该检查前置条件，即数组是否确实已排序。这也可以在O(n)的时间内完成，因此它不违反任何要求。

如果您需要找到所有可能产生所需总和的数字对而不仅仅是一对，则可能需要改进该算法。

当视频链接已经说过时，这个答案是否多余？首先，我的解释更简短，如果够用，那就没问题了。最重要的是，如果视频被删除或移动到另一个URL，我的答案仍将存在。

- Ole V.V.

---

如果有人不想通过视频链接来获取简单的解释，就像我现在这样...你的答案就在这里供我们阅读 :-) - walen

Answer 3

使用固定的number，对于数组中任选的x，您只需找到是否存在number-x在数组中（请注意，您也可以限制x）。这不会给您O(n)，但是O(n.log(n))。

也许通过注意到如果您有a_i和a_j（j>i），将它们相加并与number进行比较，如果结果更大，则下一个有趣的测试是使用a_(i-1)或a_(j-1)，如果结果更小，则下一个有趣的测试是使用a_(i+1)或a_(j+1)，将提示线性时间？

- Jean-Baptiste Yunès

---

O(n)算法使用双指针算法。 - xrisk

我不知道这个，谢谢！我重新发现了它的基础知识，但是没有时间深入挖掘。 - Jean-Baptiste Yunès

据我所记，双指针算法仅在数组排序时才有效。 - Amit Kumar

@AmitKumar，原帖中说它已经排序了。 - Enzokie

@Enzokie 我不好意思！！ - Amit Kumar