题目:
Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input : numbers={2, 7, 11, 15}, target=9
Output : index1=1, index2=2
思路：
建立一个长度为 target 大小的数组 index 作为哈希表，初值为0，key 是合成 target 的值， value 是 key 在 nums 中的下标，遍历 nums 数组，做如下操作：
基于上述思路的代码如下：
1 int* twoSum(int* nums, int numsSize, int target) { 2 int i; 3 int * index = calloc(target + 1, sizeof(int)); 4 int * result = malloc(sizeof(int) * 2); 5 6 for (i = 0; i < numsSize; ++i) { 7 if (nums[i] > target) 8 continue; 9 if (index[target - nums[i]] == 0) { 10 index[nums[i]] = i + 1; 11 continue; 12 } 13 result[0] = index[target - nums[i]]; 14 result[1] = i + 1; 15 break; 16 } 17 free(index); 18 return result; 19 }
然而这是错误的，因为输入的数组可能存在负数，我们无法找到下标为负数的数组，因此对原方法做修正：遍历一遍数组，记录最小值 minNum ，对哈希表的所有 key 做minNum 大小的偏移，那么 target 需要做 2*minNum 大小的偏移，基于此思路得到正确代码如下：
1 /** 2 * Note: The returned array must be malloced, assume caller calls free(). 3 */ 4 int* twoSum(int* nums, int numsSize, int target) { 5 int i, min = nums[0], first; 6 int * index; 7 int * result = malloc(sizeof(int) * 2); 8 9 for (i = 1; i < numsSize; ++i) { 10 if (min > nums[i]) 11 min = nums[i]; 12 } 13 target -= 2 * min; 14 index = calloc(target + 1, sizeof(int)); 15 for (i = 0; i < numsSize; ++i) { 16 first = nums[i] - min; 17 if (first > target) 18 continue; 19 if (index[target - first] == 0) { 20 index[first] = i + 1; 21 continue; 22 } 23 result[0] = index[target - first]; 24 result[1] = i + 1; 25 break; 26 } 27 free(index); 28 return result; 29 }
原文：http://www.cnblogs.com/YaolongLin/p/4849407.html
