leetcode：OJ 1.Two Sum [Difficult

题目：

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：暴力解决，时间复杂度为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为数组中最小的数min和符合条件的最大数max（由目标数减去最小数确定）之差。将满足条件的数组元素放入Hash表中，通过hash表中target-nums[i]-min来确定是否已经找到满足条件的下标，使用Hash法可以把时间复杂度降低到O(n)，不过在数组内值差别很大时不太适合此方法。例如数组有两个元素[-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;
}