問題(Question)：

今天試著寫了一下 LeetCode 這個網站裡的題目

雖然是解得出來，但是也遇到一個疑問：

就是效能的拿捏，與程式合理性之間該如何平衡？

就拿這個例子來說：

https://leetcode.com/problems/two-sum/

題目意思是說輸入一個數字陣列 numbers，與一個目標數字 target，

如何在 numbers 中找到其中兩個數字之和，剛好等於 target。

舉例而言：
Input: numbers={2, 7, 11, 15}, target=9
則答案就是：
Output: index1=1, index2=2 (第1個數字(2) + 第2個數字(7) = 9)

題目有個前提假設：
輸入的陣列 numbers 裡面，必定有兩個數字之和等於 target，所以不需要考慮錯誤處理


所以我寫了下面第一版的程式：

int* twoSum(int* nums, int numsSize, int target) {
int i, j, *x;
for(i = 1; i < numsSize; i++) {
for(j = 0; j < i; j++) {
if(nums[j] + nums[i] == target) {
x = malloc(2 * sizeof(int));
x[0] = j+1; /* index1 */
x[1] = i+1; /* index2 */
return x;
}
}
}
}

這是一個用暴力法去尋找所有兩個數字的組合，所以 time complexity = O(N^2)

後來覺得太慢了，就寫了下面的第二版：

int* twoSum(int* nums, int numsSize, int target) {
int i, diff;
int x[200001] = {0}; /* 位置 0~200000 表示 -100000~100000 之間的數字 */
int *y;
for(i = 0; i < numsSize; i++)
x[nums[i] + 100000] = i + 1; /* 儲存位置，若為 0 表示不存在 */
for(i = 0; i < numsSize; i++) {
diff = target - nums[i];
if((x[diff + 100000] != 0) && (i + 1 != x[diff + 100000])) {
y = malloc(2 * sizeof(int));
y[0] = i + 1; /* index1 */
y[1] = x[diff + 100000]; /* index2 */
return y;
}
}
}

原理是利用類似 Hash 的方法，對於有出現的數字，先儲存其位置到一個陣列中。

當已知某一數字，又知道 target 時，就可以相減而得知缺哪個數字，

再去查詢該數字是否存在，以及其位置。

這種方法的 time complexity 就比剛剛的第一版小很多



but......

問題來了......


第二版的程式雖然效能快很多，但對於運算數字的大小有其限制。

至少我在上面的程式碼之中，是假設數字應該只會出現在 -100000~100000 的範圍之內

如果這樣的程式題目出現在應徵工作時，這樣寫是否恰當？

畢竟我覺得就工作而言，任何情況都有可能發生，

或者應該其實別想這麼多，只要程式能夠 work 就行？
(至少這個版本，我在 LeetCode 裡面是有通過驗證的)

想請教各位高手，對於這一點的看法...

謝謝！


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.161.161.233
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1436809890.A.F01.html