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.

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

我的答案：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target) {
    for(int i=0; i<numsSize; i++){
        for(int j=i+1;j<numsSize; j++){
            if(nums[i]+nums[j]==target){
                int *result = (int *)malloc(sizeof(int)*2);
                result[0] = i;
                result[1] = j;
                return result;
            }
        }
    }
    return NULL;
}

性能：
時(shí)間復(fù)雜度：O(n2)
runtime:89ms
beats 76.01% submissions

網(wǎng)上優(yōu)秀答案：

int* twoSum(int* nums, int numsSize, int target) {
    int array[100000] = {-1};
    int temp = 0;
    int i = 0;
    static int result[2];
    for(i = 0; i < numsSize; i++) {
        array[nums[i] + 5000] = i;
    }
    for(i = 0; i < numsSize; i++) {
        temp = array[target - nums[i] + 5000];
        if(temp)
            if(temp > i) {
                result[0] = i;
                result[1] = temp;
                break;
            }
    }
    return result;
}

性能：
時(shí)間復(fù)雜度：O(n)
runtime:3ms
beats 94.38% submissions
犧牲空間復(fù)雜度換取時(shí)間復(fù)雜度
Java、C++ 有現(xiàn)成的HashMap