@[王宏宇11](/space/show?uid=123168) 排序完对每个数来一遍双指针，$O(n^2)$，不排序暴力是$O(n^3)$
by ddwqwq @ 2018-12-25 00:08:46
刚刚入门，对于空间复杂度都不是很了解，复杂度使用来干嘛的，望大佬指导
by 王宏宇11 @ 2018-12-25 00:20:11
百度啊
by EMT__Mashiro @ 2018-12-25 08:26:25
可以用NTT（逃）
by ytxytx @ 2018-12-25 11:57:24
你是小白，咱们就通俗点说，我们看这个有序数列：
1 2 3 4 5 6 7 8 9
由于是从小到大，所以和一定在两个加数后面，因为和一定比两个加数大。所以遍历的时候，i从头开始，j从i的后一个开始，而k就只需要从j的后一个开始就行了，不需要从头开始，而i甚至不需要遍历整个数组，当i大于最大的数字的一半的时候，就可以不用再遍历了（例如这个题i只需要到4，而5无论加后面的谁都会超过9，不可能有结果），这样能大大减少运算量，相比而言，快排消耗的那点时间，就微不足道了。
而如果是无序的序列：
8 5 2 3 6 9 7 4 1
你每次都必须从头一个一个试，因为k不一定在哪，i也只能从头到尾扫一遍，这样会浪费很多的时间。几乎比那个多出了一层循环的时间。所以，先排序是基本思路，有序数列的优点太多了。
by Clairad @ 2018-12-27 18:12:24