算法的运行时间优化

Question

我正试图找到一种方法来优化我的算法,使运行时间为O(n²)(Big O Notation).

输入是一个包含n个元素的数组,只有正整数和负整数.我们可以假设数组已经排序.

我必须确定:对于每个r(数组的元素),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;
}

Answer 1

您可以开始对数组进行排序O(nlogn)（如果没有），然后对于数组中的每个元素，您可以检查是否有两个元素的总和等于中的数字O(n\xc2\xb2)。

\n\n

代码是C#的的：

\n\n

public static bool Solve(int[] arr)\n{\n    Array.Sort(arr);    //If not already sorted\n\n    foreach (var num in arr)\n        if (!FindTwoThatSumN(arr, num))\n            return false;\n\n    return true;\n}\n\npublic static bool FindTwoThatSumN(int[] arr, int num)\n{\n    int min = 0;\n    int max = arr.Length - 1;\n\n    while (true)\n    {\n        if (min == max) break;\n\n        int sum = arr[min] + arr[max];\n\n        if (sum < num) min++;\n        if (sum > num) max--;\n        if (sum == num) return true;\n    }\n\n    return false;\n}\n

\n\n

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

\n\n

\n
• 如果总和小于数字，则增加min索引。
\n
• 如果总和大于数字，则减少max索引。
\n
• 如果总和等于数字，那么您就找到了解决方案。
\n
• 如果min指数达到max则无解。
\n

\n\n

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

\n\n

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

\n\n

\n
• 对数组进行排序：O(nlogn) .
\n
• 迭代排序后的数组：O(n) .
\n
• 找出两个数字的总和：O(n)。
\n

\n\n

所以，是O(n\xc2\xb2)由于嵌套调用FindTwoThatSumN。

\n\n

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

\n