博客

**

有人相爱，有人夜里开车看海，有人leetcode第一题都做不出来。

**

首先第一眼，没有思路

然后看了解答

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum/*两数之和*/(int* nums/*整数数组*/, int numsSize/*和值*/, int target/*整数目标值*/  , int* returnSize/*目标值数组下标*/){
    //两个for循环遍历得到和值：numsSize，并与target值比较，相等则输出i，j
    int i,j;
for (i=0;i<*nums;i++)
{
    for(j=i;j<*nums;j++)
    {
        if( nums[i]+nums[j]=target)
       { ret=malloc(size(int));
        ret[0]=i;
        ret[1]=j;
        return ret;
       }
    }
}

当然，这个编译错误

下面是标准答案，暴力查找

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

哈希表解法

struct hashTable {
    int key;
    int val;
    UT_hash_handle hh;
};

struct hashTable* hashtable;

struct hashTable* find(int ikey) {
    struct hashTable* tmp;
    HASH_FIND_INT(hashtable, &ikey, tmp);
    return tmp;
}

void insert(int ikey, int ival) {
    struct hashTable* it = find(ikey);
    if (it == NULL) {
        struct hashTable* tmp = malloc(sizeof(struct hashTable));
        tmp->key = ikey, tmp->val = ival;
        HASH_ADD_INT(hashtable, key, tmp);
    } else {
        it->val = ival;
    }
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    hashtable = NULL;
    for (int i = 0; i < numsSize; i++) {
        struct hashTable* it = find(target - nums[i]);
        if (it != NULL) {
            int* ret = malloc(sizeof(int) * 2);
            ret[0] = it->val, ret[1] = i;
            *returnSize = 2;
            return ret;
        }
        insert(nums[i], i);
    }
    *returnSize = 0;
    return NULL;
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。