leetcode的第一题

暴力解题法

#include <stdio.h>
#include <stdlib.h>

/**
 * @brief 从给定的整数数组中找出两个数，使得它们的和等于目标值。
 *
 * 此函数通过双重循环遍历数组，检查每对可能的元素组合。
 * 当找到两个元素的和等于目标值时，将它们的索引存储在动态分配的数组中并返回。
 * 如果没有找到这样的组合，则返回 NULL。
 *
 * @param nums 指向整数数组的指针，该数组包含要搜索的元素。
 * @param numsSize 数组的大小，表示数组中元素的数量。
 * @param target 目标和，即需要找到的两个元素的和。
 * @param returnSize 指向整数的指针，用于存储返回数组的大小（通常为 2 或 0）。
 * @return 指向包含两个索引的整数数组的指针，如果找到匹配项；否则返回 NULL。
 */
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* result = (int*)malloc(2 * sizeof(int));
                result[0] = i;
                result[1] = j;
                *returnSize = 2;
                return result;
            }

        }
    } 
    *returnSize = 0;
    return NULL;
}

    


int main() 
{
    int nums[] = {2, 7, 11, 15};   
    int returnSize;
    int* result = twoSum(nums, 4, 9, returnSize);
    if (result != NULL) 
    {
        printf("[%d %d]\n", result[0], result[1]);
        free(result);
    }

    return 0;

}

哈希表

#include <stdio.h>
#include <stdlib.h>
#include "uthash.h"



struct hashTable {
    int key;  //key 是要存入哈希表的键（此处是数组中的值）。
    int val; //val 是与键相关联的值（此处是数组中的索引）。
    UT_hash_handle hh; //hh 是哈希表节点的句柄，用于在哈希表中进行节点的插入、删除等操作。
};

struct hashTable* hashtable;  //hashtable 是哈希表的头指针，用于指向哈希表的第一个节点。


/**
 * 在哈希表中查找给定整数键的节点。
 * 
 * 此函数使用 UTHash 库的宏 HASH_FIND_INT 来在哈希表中查找指定键的节点。
 * 如果找到匹配的节点，则返回指向该节点的指针；否则返回 NULL。
 * 
 * @param ikey 要查找的整数键。
 * @return 返回指向找到的节点的指针，如果未找到则返回 NULL。
 */
struct hashTable* find(int ikey) {
    struct hashTable* tmp;              // tmp 是一个临时指针，用于遍历哈希表中的节点。
    HASH_FIND_INT(hashtable, &ikey, tmp);  // HASH_FIND_INT 是 UTHash 库提供的宏，用于在哈希表中查找指定键的节点。哈希表中查找该键对应的节点，并将其赋值给 tmp 指针。
    return tmp;  
}

/**
 * 插入键值对到哈希表中
 * 如果键已存在，则更新其值
 * 如果键不存在，则创建并插入新的键值对
 * 
 * @param ikey 要插入或更新的键
 * @param ival 与键关联的值
 */
void insert(int ikey, int ival) {
    // 尝试在哈希表中查找给定键的条目
    struct hashTable* it = find(ikey);
    if (it == NULL) {
        // 如果键不存在，分配新的哈希表条目
        struct hashTable* tmp = (struct hashTable*)malloc(sizeof(struct hashTable));
        if (tmp == NULL) {
            // 处理内存分配失败的情况
            fprintf(stderr, "Memory allocation failed\n");
            exit(EXIT_FAILURE);
        }
        // 初始化新条目的键和值
        tmp->key = ikey;    //key 是要存入哈希表的键（此处是数组中的值）
        tmp->val = ival;    //val 是与键相关联的值（此处是数组中的索引）
        // 使用HASH_ADD_INT宏将新条目添加到哈希表中
        HASH_ADD_INT(hashtable, key, tmp);
    } else {
        // 如果键已存在，更新其值
        it->val = ival;
    }
}

/**
 * 使用哈希表解决Two Sum问题。
 * 
 * 该函数旨在从给定的整数数组中找出两个数，使它们的和等于目标值target。
 * 它通过使用哈希表来记录每个数字是否 previously encountered 来实现。
 * 
 * @param nums 给定的整数数组。
 * @param numsSize 数组中元素的数量。
 * @param target 目标值，即两数之和应该等于的值。
 * @param returnSize 指针，用于返回结果数组的大小。如果未找到满足条件的数对，设置为0；如果找到，设置为2。
 * @return 如果找到满足条件的数对，返回指向包含这两个数的索引的数组；如果未找到，返回NULL。
 * 
 * 注意：该函数内部使用了辅助函数`find`和`insert`来操作哈希表，这些函数的实现细节在此未给出。
 */
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 = (int*)malloc(sizeof(int) * 2);
            if (ret == NULL) {
                // 处理内存分配失败的情况
                fprintf(stderr, "Memory allocation failed\n");
                exit(EXIT_FAILURE);
            }
            // 分配成功后，填充结果数组并返回
            ret[0] = it->val;
            ret[1] = i;
            *returnSize = 2;
            return ret;
        }
        // 如果未找到，将当前数字及其索引插入哈希表
        insert(nums[i], i);
    }
    // 如果遍历完数组仍未找到满足条件的数对，设置returnSize为0并返回NULL
    *returnSize = 0;
    return NULL;
}

// 测试函数
int main() {
    int nums[] = {2, 7, 11, 15};
    int target = 9;
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int returnSize;

    int* result = twoSum(nums, numsSize, target, &returnSize);

    if (returnSize == 2) {
        printf("[%d %d]\n", result[0], result[1]);
    } else {
        printf("No solution found.\n");
    }

    free(result); // 释放动态分配的内存
    return 0;
}