Friday, October 17, 2008

请教一道面试题

http://www.mitbbs.com/article_t/JobHunting/31310332.html
一个SORTED ARRAY,例如 A[]={0, -10, 20, 30, 40, 50, -60, 70, 80, 90, 100}(注意是按绝对值来排序),一个数NUM,求所有相加等于NUM的两个数的组合,例如NUM=40,答案是{0,40},{-10, 50},{-60, 100}。要求O(N)。感觉要是按大小来排序还好办,但按绝对值来排序我就糊涂了,请高手指教。
No extra storage space, so no hash table.

No comments: