int* twoSum(int* nums, int numsSize, int target) { //int可表達有號最大正整數值為2147483647,此處可得到數組最小值min int min = 2147483647; int i = 0; for( i = 0; i < numsSize; i ++) { if( nums[i] < min ) min = nums[i]; } //target為兩數相加,扣掉min後,另一解為max(不可能比max大) int max = target - min; //len為hash長度,最差情況是max到min之間的數都相差1 //意義為從min開始往後找len個數值以內,一定可以找到max為解 int len = max - min + 1; int *ans = (int*)malloc(2*sizeof(int)); int *table = (int*)malloc(len*sizeof(int)); //初始化table,因為不保證每一格都會用到,避免不可預期的錯誤 for (i = 0; i < len; i++) { table[i] = -1; } for( i = 0; i < numsSize; i++) { //不需考慮比max大的解 if( nums[i] < max + 1 ) { //target-min=另一解的最大值,再-nums[i]後,若查表得知table已更動過 //表示此解已被尋訪過,就找到解答了 if( table[target - min - nums[i]] != -1) { ans[0] = table[target - min - nums[i]]; ans[1] = i; return ans; } //若查表得知table未更動過,表示此解尚未被尋訪,則修改table值 table[nums[i] - min] = i; } } return ans; }