搜索未排序数组以求和为一个值的3个元素

Question

我正在尝试制定Θ（n²）的算法。它接受n个元素的未排序数组和一个整数[[z，并且必须返回3个3个[[different元素a，b，c的索引；所以a + b + c = z （如果找不到这样的整数，则返回NILL）

我试图先以两种方式对数组进行排序，然后搜索排序后的数组。但是由于其余算法需要特定的运行时间，所以我迷路了。 有没有排序的方法吗？ （我想它必须要排序）有或没有排序都很好。

示例

：对于此数组：1, 3, 4, 2, 6, 7, 9和整数6

它必须返回：0, 1, 3

因为（1 + 3 + 2 = 6）

Answer 1

算法绝不直观！

排序-O（nlogn）

对于i = 0 ... n-1-O（1）向i赋值
1. new_z = z-array [i]该值在每次迭代时更新。现在，使用两个指针从头开始（索引0）和结束（索引n-1）对new_z进行二进制搜索。如果sum大于new_z，则从顶部的指针中减去1。如果较小，则加1开始指针。否则，返回i，表示当前的结束位置并开始。 -O（登录）
2. i = i + 1并跳至步骤2-O（1）

步骤2、3和4的成本为O（nlogn）。总体而言，O（nlogn）