1. 两数之和

- 2 mins read

1. 两数之和

LeetCode 1. 两数之和

题目描述

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例

  • 示例 1

    输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

  • 示例 2

    输入：nums = [3,2,4], target = 6
输出：[1,2]

  • 示例 3

    输入：nums = [3,3], target = 6
输出：[0,1]

解题模版

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
}

解题思路

  1. 使用一个HASH表结构,遍历数组nums.
  2. 使用 c = target - nums[i] 在 HASH表中查找。
  3. 没有找到将key = nums[i], value = i添加到HASH表
  4. 如果找到，返回当前下标和查找到的下标

解答

typedef struct {
    int key;
    int value;
    UT_hash_handle hh;
} HashNode;
void put(HashNode **hash_map, int key, int value) {
    HashNode *tmp = NULL;
    tmp = (HashNode*)malloc(sizeof(HashNode));
    tmp->key = key;
    tmp->value = value;
    HASH_ADD_INT(*hash_map, key, tmp);
}

void delete(HashNode **hash_map, HashNode *t) {
    HASH_DEL(*hash_map, t);
    free(t);
    t = NULL;
}

HashNode* find(HashNode **hash_map, int key) {
    HashNode *tmp = NULL;
    HASH_FIND_INT(*hash_map, &key, tmp);
    return tmp;
}

void clean_all(HashNode **hash_map) {
    HashNode *s, *tmp;
    HASH_ITER(hh, *hash_map, s, tmp)
    {
        delete(hash_map, s);
    }
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int* result = NULL;
    if(numsSize < 2) {
        return result;
    }
    HashNode **hash_map = NULL;
    hash_map = (HashNode**)malloc(sizeof(HashNode*));
    *hash_map = NULL;
    for(int i = 0; i < numsSize; i++) {
        int c = target - nums[i];
        HashNode* t = find(hash_map, c);
        if(t != NULL) {
            result = (int*) malloc(sizeof(int) * 2);
            result[0] = t->value;
            result[1] = i;
            *returnSize = 2;
            break;
        }
        put(hash_map, nums[i], i);
    }
    clean_all(hash_map);
    free(hash_map);
    return result;
}

Contents