leetcode:Two Sum

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

看到题目，我想，这还不简单吗，两个for循环就搞定了呀！！！

刷刷写上代码，改正小错误后，leetcode告诉我：time Limit Exceeded。

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target) {
    int i, j;
    int *r = malloc(sizeof(int) * 2);

    for (i = 0; i < numsSize; i++) {
        int value = target - nums[i];
        for (j= i + 1; j < numsSize; j++) {
            if (nums[j] == value) {
                r[0] = i + 1;
                r[1] = j + 1;
                return r;
            }
        }
    }
    free(r);
    return NULL;
}

我不被接受啊，居然还需要优化！！！

我想想，貌似只能优化第二个循环了的查找了，写一个hash吧。

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */



struct solt {
    int value;
    int pos;
    struct solt *next;
};

struct solt ** create(int *nums, int numsSize) {
    int i = 0;
    struct solt ** head = calloc(numsSize, sizeof(struct solt *));
    for (i = 0; i < numsSize; i++) {
        int key = nums[i] % numsSize;
        key = key > 0 ? key : (-1 * key);
        struct solt *s = calloc(1, sizeof(struct solt));
        s->value = nums[i];
        s->pos = i;
        if (head[key] != NULL) {
            s->next = head[key];
        }
        head[key] = s;
    }
    return head;
}

int soltFind(struct solt ** head, int numsSize, int value) {
    int key = value % numsSize;
    key = key > 0 ? key : (-1 * key);
    struct solt * s = head[key];
    while (s != NULL) {
        if (s->value == value) {
            return s->pos;
        }
        s = s->next;
    }
    return -1;
}

void soltFree(struct solt **head, int numsSize) {
    int i = 0;
    for (i = 0; i < numsSize; i++) {
        struct solt *s = head[i];
        while (s) {
            struct solt * st = s->next;
            free(s);
            s = st;
        }
    }
    free(head);
}

int* twoSum(int* nums, int numsSize, int target) {
    int i, j;
    int *r = malloc(sizeof(int) * 2);
    struct solt ** head = create(nums, numsSize);
    for (i = 0; i < numsSize; i++) {
        int value = target - nums[i];
        int j = soltFind(head, numsSize, value);
        if (j >=0 && j != i) {
            soltFree(head, numsSize);
            r[0] = i + 1;
            r[1] = j + 1;
            return r;
        }
    }
    soltFree(head, numsSize);
    free(r);
    return NULL;
}

leetcode:Two Sum

原文：http://blog.csdn.net/gamesofsailing/article/details/45601453