※ 引述《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