算法的运行时间优化
我试图找到一种方法来优化我的算法，使得运行时间为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;
}
您可以开始对数组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) 。 因此，由于嵌套调用FindTwoThatSumN ，因此是O(n²) 。
如果您想要，您可以将索引而不是数字传递给FindTwoThatSumN方法，以避免额外的检查将数字本身用作解决方案的一部分。
set.contains在常量时间内运行。