我有作业要做。 我必须实现一个算法，该算法必须检查大小为 N 的 ArrayList 中是否至少有两个数字相加，它们的总和为 N。 算法的复杂度必须是 Theta(n log n)。 我已经知道我可以使用 Merge.Sort 或堆排序，然后我必须用数组列表的每个元素减去数组列表的大小。 问题是:按顺序减去复杂性，仍然是 Theta(n log n)？!？ 如果不是，我该如何保持这种状态？
最佳答案
使用任何排序算法对数组进行排序，最好是具有可接受顺序的算法，例如 mergeSort，它是 (O(nlogn));
然后开始检查数组的第一个和最后一个元素并保留它们的索引，即“开始”和“结束”。 当最后一个元素大于您想要的值时，将索引减一，然后将“开始”和“结束”的总和与您想要的值进行比较，
如果它大于你想要的值，你将找不到任何两个满足你条件的值，
如果它等于你想要的值，报告'开始'和'结束'元素
如果它小于您想要的值，则增加“开始”索引 并再次进行比较，
重复直到两个索引相遇。
最终复杂度为:O(n) + O(nlogn) 等于 O(nlogn)
关于algorithm - 检查大小为 N 的 ArrayList 中是否有两个数字的总和为 N，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/50104209/