1. 两数之和

难度：简单

题目

给定一个整数数组nums和一个目标值target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

Reference

题解

基本思路：

将数组中的元素存储在哈希表中，每次在数组中查找目标值与当前值之差是否在哈希表中。

代码如下：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
#define MAX(a, b) (a > b ? a : b)
#define MIN(a, b) (a < b ? a : b)
struct cell
{
    int value;
    int flag;
};
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    *returnSize = 2;
    int i = 0, mapSize = numsSize * 2, cur, *ret = malloc(sizeof(int) * 2), targetval, j = 0;
    struct cell *hashMap = (struct cell *)memset(malloc(sizeof(struct cell) * mapSize), 0, sizeof(struct cell) * mapSize);
    for (i = 0; i < numsSize; i++)
    {
        cur = (nums[i] > 0 ? nums[i] : -nums[i]) % mapSize;
        while(hashMap[cur].flag != 0 && hashMap[cur].value != nums[i])
        {
            cur++;
            cur = cur == mapSize ? 0 : cur;
        }
        if (hashMap[cur].flag == 0)
            hashMap[cur].value = nums[i];
        hashMap[cur].flag++;
    }
    for (i = 0; i < numsSize; i++)
    {
        targetval = target - nums[i];
        cur = (targetval > 0 ? targetval : -targetval) % mapSize;
        while(hashMap[cur].flag != 0 && hashMap[cur].value != targetval)
        {
            cur++;
            cur = cur == mapSize ? 0 : cur;
        }
        if (hashMap[cur].value == targetval)
        {
            for (j = 0; j < numsSize; j++)
                if (nums[j] == targetval && j != i)
                    break;
            if (j != numsSize)
                break;
        }
    }
    ret[0] = MIN(i, j);
    ret[1] = MAX(i, j);
    if (nums[i] + nums[j] == target)
        return ret;
    *returnSize = 0;
    return NULL;
}

评论