C语言实现LeetCode两数之和问题：优化解法及代码示例

本文将介绍如何使用C语言解决LeetCode上的'两数之和'问题，并提供一个优化的解法以及详细的代码示例。

问题描述:

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

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

示例:

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

优化解法：哈希表

使用哈希表可以将查找时间复杂度降低到 O(n)，因为哈希表可以在常数时间内完成查找操作。

**代码示例:**c#include <stdio.h>#include <stdlib.h>

// 定义哈希表节点结构体struct Node { int key; int val; struct Node *next;};

// 哈希函数int hash(int key, int size) { return abs(key) % size;}

// 插入键值对到哈希表void insert(struct Node **hashTable, int key, int val, int size) { int index = hash(key, size); struct Node *newNode = (struct Node *)malloc(sizeof(struct Node)); newNode->key = key; newNode->val = val; newNode->next = hashTable[index]; hashTable[index] = newNode;}

// 在哈希表中查找键对应的值int search(struct Node **hashTable, int key, int size) { int index = hash(key, size); struct Node *curr = hashTable[index]; while (curr != NULL) { if (curr->key == key) { return curr->val; } curr = curr->next; } return -1;}

// 两数之和函数int *twoSum(int *nums, int numsSize, int target, int *returnSize) { int hashTableSize = numsSize * 2; // 设置哈希表大小 struct Node **hashTable = (struct Node **)calloc(hashTableSize, sizeof(struct Node *)); for (int i = 0; i < numsSize; i++) { int complement = target - nums[i]; int index = search(hashTable, complement, hashTableSize); if (index != -1) { // 找到匹配的数 *returnSize = 2; int *result = (int *)malloc(*returnSize * sizeof(int)); result[0] = index; result[1] = i; // 释放哈希表内存 for (int j = 0; j < hashTableSize; j++) { struct Node *curr = hashTable[j]; while (curr != NULL) { struct Node *temp = curr; curr = curr->next; free(temp); } } free(hashTable); return result; } insert(hashTable, nums[i], i, hashTableSize); // 将当前数插入哈希表 }

*returnSize = 0;    // 释放哈希表内存    for (int j = 0; j < hashTableSize; j++) {        struct Node *curr = hashTable[j];        while (curr != NULL) {            struct Node *temp = curr;            curr = curr->next;            free(temp);        }    }    free(hashTable);    return NULL;}

int main() { int nums[] = {2, 7, 11, 15}; int target = 9; int returnSize; int *result = twoSum(nums, sizeof(nums) / sizeof(nums[0]), target, &returnSize);

if (returnSize == 2) {        printf('[%d, %d]

', result[0], result[1]); } else { printf('未找到符合条件的数字对 '); }

free(result);    return 0;}

代码解释:

哈希表实现: 代码中定义了 Node 结构体表示哈希表节点，包含键值对和指向下一个节点的指针。hash 函数计算键的哈希值，insert 函数将键值对插入哈希表，search 函数在哈希表中查找键对应的值。2. twoSum 函数: - 首先创建一个哈希表 hashTable，用于存储数组元素及其索引。 - 遍历数组 nums，对于每个元素 nums[i]，计算其与目标值 target 的差值 complement。 - 在哈希表中查找 complement 是否存在： - 如果存在，则找到了目标数字对，返回它们的索引。 - 如果不存在，则将 nums[i] 及其索引 i 插入哈希表。3. 主函数 main: - 定义输入数组 nums 和目标值 target。 - 调用 twoSum 函数计算结果，并打印结果索引。

总结:

使用哈希表可以有效地解决'两数之和'问题，时间复杂度为 O(n)。理解哈希表的原理和实现对于解决类似问题非常有帮助。