起始值 book array index: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10 value:-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2 counter = 0, input = 5, -->book array[10-5] = -2 -->之前没有过5 -->先不print -->填入book array[5] = counter = 0 book array index: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10 value:-2,-2,-2,-2,-2, 0,-2,-2,-2,-2,-2 counter = 1, input = 5, -->book array[10-5] = 0 --> counter = 0的时候有过5 --> 要补print -->所以print 55, 55 -->填入book array[5] = -1 //-1代表已经有配对成功过 book array index: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10 value:-2,-2,-2,-2,-2,-1,-2,-2,-2,-2,-2 counter = 2, input = 7, -->book array[10-7] = -2 -->之前没有过3 -->先不print -->填入book array[7] = counter = 2 book array index: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10 value:-2,-2,-2,-2,-2,-1,-2, 2,-2,-2,-2 counter = 3, input = 12, --> 12 > 10, 直接skip counter = 4, input = 3, -->book array[10-3] = 2 --> counter = 2的时候有过7 --> 要补print -->所以print 73, 37 -->填入 book array[7] = book array[3] = -1 //-1代表已经有配对成功过 book array index: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10 value:-2,-2,-2,-1,-2,-1,-2,-1,-2,-2,-2 counter = 5, input = 5, -->book array[10-5] = -1 -->之前有过且已经配对过 -->不用补print -->print 55 -->填入 book array[5] = -1 //虽然已经填过... book array index: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10 value:-2,-2,-2,-1,-2,-1,-2,-1,-2,-2,-2 依此类推.... 希望没有bug... Time应该是O(N), memory应该是O(K), K是想要求的总合, 这里是10, 不随着N增加 基本逻辑就是 -2代表从来没有这数字过 -1代表之前有过这数字且配对成功过 其他正值代表之前有过一次 还没有配对过.. (其实如果不在乎是在哪时出现过 也可以都用0) 每次数字进来 就去找他的真命天子出现过了没 没出现过(-2)-->就住回自己的房子 (book array[input] = counter) 有出现过且没配对过(正值)-->恭喜配对成功 要补print, print 两组 -->把双方的房子都标示配对成功(-1) 有出现过但已经有对象(-1)-->单相思, print一组 然後一值这样下去..... ※ 引述《nukchichi (haha)》之铭言： : 大家好, : 今天phone interview某间大公司的小 entry level Software developer. : 考到一个问题...想分享出来且寻求答案. : == : 给数字 5, 5, 7, 12, 3, 5 : 如何找出并印出里面是两个和 sum = 10的数字组(pair) : 他给的printpair 的 output是 55 55 73 55 (但是我後来想 应该有少给我37...) : == : 我一开始没有想法 但是时间压力 就直接先给他直观的做法 : 两个for loop 检查, : 第一次回圈 用10-5 = 5 去找数组里其他的5 找到就印出 : 2nd 10 - 5 = 5 去找其他的5 : 3nd 10 - 7 = 3 去找其他的3 : ... : 这样他说可以, 但是希望能更好. 我想了想 想不太出来请他能提示 : 他说: 想想为何我刚刚问你比较 link list, binary tree, 和hash table. : 我直觉是要用hashtable去找(他好像也认同我用hashtable) : 但是他要我把hashtable的样子跟他讲 exactly 一点~ : 我就答不出来了...然後就byebye了... : == : 烦请版友帮忙我这新手解答疑惑... : 感谢!! --

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