題目：
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,return [0,1].
方法1：暴力解決掖桦，時間復(fù)雜度為O(n^2)俐芯。
int* twoSum(int* nums, int numsSize, int target) {
int *result = (int*)malloc(sizeof(int)*2);
for(int i = 0;i < numsSize-1;i++){
for(int j = i+1;j < numsSize;j++){
int sum = nums[i] + nums[j];
if(sum == target){
result[0] = i;
result[1] = j;
}
}
}
return result;
}
方法2：哈希查找
原理是先取一段len長度的hash表涩澡，len為數(shù)組中最小的數(shù)min和符合條件的最大數(shù)max（由目標(biāo)數(shù)減去最小數(shù)確定）之差医咨。將滿足條件的數(shù)組元素放入Hash表中概耻，通過hash表中target-nums[i]-min來確定是否已經(jīng)找到滿足條件的下標(biāo)，使用Hash法可以把時間復(fù)雜度降低到O(n)，不過在數(shù)組內(nèi)值差別很大時不太適合此方法。例如數(shù)組有兩個元素[-1000,1000],弹谁，分配空間就太大，效率不高句喜。
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* twoSum(int* nums, int numsSize, int target) {
int min = 23333333;
for(int i = 0;i < numsSize;i++){
if(nums[i] < min){
min = nums[i];
}
}
int max = target - min;
int len = max - min + 1;
int *table = (int*)malloc(len * sizeof(int));
int *choice = (int*)malloc(2 * sizeof(int));
for(int i = 0;i < len;i++){
table[i] = -1;
}
for(int i = 0;i < numsSize;i++){
if(nums[i] - min < len){
if(table[target-nums[i]-min] != -1){
choice[0] = table[target - nums[i] - min];
choice[1] = i;
return choice;
}
table[nums[i] - min] = i;
}
}
free(table);
return choice;
}
