※ 引述《DJWS (...)》之铭言： : 这边提供一个另类的想法。 : 想像一个二维阵列 sum[i][j] = array[i] + array[j] : 可以发现往右往下 sum 会变大，往左往上 sum 会变小， : 其实 sum 就是一个排序过的二维阵列。 : 在 sum 里面做 binary search 需要 O(N) 时间。 : 套用前面 LPH66 与 stimim 板友推文里的解法， : 穷举 array 的每一个数字，在 sum 里面二分搜寻， : 总共就是 O(NN) 时间了。 : 那麽能不能更快呢？我也不知道... : 穷举 array 的每一个数字，是由小到大穷举的话， : 每一个数字在 sum 里面的二分搜寻路线，就是逐渐偏右、偏下， : 这些路线应该会有很多地方重叠， : 如果可以把重叠的路线省略掉的话，应该可以更快吧？ : 以上 嘛...其实我想到的做法有点不太对称 我是一次固定一个数字 另一个数字用类似 merge sort 的方式往後扫 虚拟码大概像这样 for(i = 0 ... n-1) { j = 0 k = 0 while(j < n && k < n) { if(array[i] + array[j] < array[k]) j++; else if(array[i] + array[j] > array[k]) k++; else {print Found [i] + [j] = [k]; exit} } } print Not Found 中间那层 while 因为 j++ 和 k++ 最多各 n 次 所以是 O(n) 因此全部就是 O(n^2) 这样 说是不对称是因为我列举的是 [i] 上面那个列举的是 [k] 这样而已... -- 1985/01/12 三嶋鸣海 1989/02/22 优希堂悟 1990/02/22 冬川こころ 1993/07/05 小町 つぐみ 欢迎来到 1994/05/21 高江ミュウ 1997/03/24 守野いづみ 1997/03/24 伊野瀬 チサト 1998/06/18 守野くるみ 打越钢太郎的 1999/10/19 楠田ゆに 2000/02/15 樋口遥 2002/12/17 八神ココ 2011/01/11 HAL18於朱仓岳坠机 ∞与∫的世界 2011/04/02 茜崎空 启动 2012/05/21 第貮日蚀计画预定 2017/05/01~07 LeMU崩坏 2019/04/01~07 某大学合宿 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.28.91