算法的运行时间优化

Question

我正在尝试找到一种优化算法的方法，使其运行时间为O(n²)（大O符号）。

输入是一个由n个元素组成的数组，只包含正数和负数。我们可以假设数组已经排序好了。

我需要确定：对于每个r（数组的元素），是否存在s和t（也是数组的元素），使得r = s + t，并且s和t可以相同（s == t），也可以都为零。

我试图通过检查当前数字是正数还是负数来减少我必须检查的元素数量，但运行时间仍然太长。问题在于我使用了3个while循环，这已经意味着最坏情况下的运行时间为O(n³)。

以下是我的代码：

public static void Checker(int[] array) {
    List<Integer> testlist = new ArrayList<Integer>();
    int i = 0;
    while (i < array.length) {
        int current = array[i];
        if (attached(current, array)) {
            testlist.add(current);
        }
        i++;
    }
}

public static boolean attached(int current, int[] array) {
    boolean result = false;
    int i = 0;
    while (i < array.length && !result) {
        int number1 = array[i];
        int j = 0;
        while (j < array.length && !result) {
            int number2 = array[j];
            if (number1 + number2 == current) {
                result = true;
            }
            j++;
        }
        i++;
    }
    return result;
}

- Elfie

---

首先，将数组中的所有元素添加到 HashSet 中，然后迭代 s 和 t 并检查是否在您的集合中呈现了 s + t。 - michael-tkach

请不要使用代码格式化或高亮显示，这样会使阅读变得非常困难。 - Esoteric Screen Name

Answer 1

1. 计算所有可能的 s+t 的和，并将结果放入一个集合中 => O(n²)
2. 迭代每个 r 并检查是否有与 r 匹配的和 => O(n)，因为 set.contains 的时间复杂度为常数。

- assylias

Answer 2

你可以开始对数组进行排序，时间复杂度为O(nlogn)（如果还没有排序的话），然后对于数组中的每个元素，你可以检查是否存在两个元素的和等于O(n²)中的数字。

以下是C#代码：

public static bool Solve(int[] arr)
{
    Array.Sort(arr);    //If not already sorted

    foreach (var num in arr)
        if (!FindTwoThatSumN(arr, num))
            return false;

    return true;
}

public static bool FindTwoThatSumN(int[] arr, int num)
{
    int min = 0;
    int max = arr.Length - 1;

    while (true)
    {
        if (min == max) break;

        int sum = arr[min] + arr[max];

        if (sum < num) min++;
        if (sum > num) max--;
        if (sum == num) return true;
    }

    return false;
}

从最小值（min = 0）和最大值（max = arr.Length）开始，检查数组中是否有两个数字（必须排序），其总和为特定值的想法是，在每次迭代中：

• 如果总和小于该数字，则增加min索引。
• 如果总和大于该数字，则减少max索引。
• 如果总和等于该数字，则找到一个解决方案。
• 如果min索引达到max，则没有解决方案。

您可以参考此问题/答案以获取更多详细信息和证明。

整体解决方案的时间复杂度为O(n²)：

• 对数组进行排序：O(nlogn)。
• 遍历排序后的数组：O(n)。
• 查找两个数字的总和：O(n)。

因此，O(n²)是由于对FindTwoThatSumN的嵌套调用造成的。

如果您希望，可以将索引传递而不是数字到FindTwoThatSumN方法，以避免使用数字本身作为解决方案的一部分时进行额外的检查。

- Arturo Menchaca