当前位置：首页 > news >正文

【LeetCode】1. 两数之和（Two Sum）— 哈希表经典题解（C语言）

news 2026/5/12 3:34:16

一、题目描述

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

你可以假设每种输入只会对应一个答案，并且同一个元素不能使用两次。

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

示例 1

输入: nums = [2,7,11,15], target = 9 输出: [0,1] 解释: nums[0] + nums[1] == 9

示例 2

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

示例 3

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

提示

2 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
-10⁹ ≤ target ≤ 10⁹
只会存在一个有效答案

二、解题思路

这道题是LeetCode 最经典的哈希表题目之一，也是很多面试的入门题。

常见解法有两种：

1️⃣ 暴力枚举
2️⃣ 哈希表优化（推荐）

三、方法一：暴力枚举

思路

最直接的方法就是两层循环枚举所有组合：

第一个循环选择第一个数nums[i]
第二个循环选择第二个数nums[j]
判断：

nums[i] + nums[j] == target

如果成立，则返回两个下标。

动图思路

假设数组：

[2,7,11,15]

target = 9

枚举过程：

2 + 7 = 9 ✔

[0,1]

C语言代码

#include <stdlib.h> int* twoSum(int* nums, int numsSize, int target, int* returnSize) { int* res = (int*)malloc(sizeof(int) * 2); for(int i = 0; i < numsSize; i++) { for(int j = i + 1; j < numsSize; j++) { if(nums[i] + nums[j] == target) { res[0] = i; res[1] = j; *returnSize = 2; return res; } } } *returnSize = 0; return NULL; }

复杂度分析

复杂度	数值
时间复杂度	O(n²)
空间复杂度	O(1)

当数组较大时，效率会明显下降。

四、方法二：哈希表（推荐）⭐

核心思想

如果：

a + b = target

那么：

b = target - a

遍历数组时：

计算当前数需要的补数

complement = target - nums[i]

查询哈希表中是否存在该补数

如果存在 → 找到答案
如果不存在 → 将当前数字存入哈希表

这样只需要遍历一次数组。

执行过程示例

数组：

[2,7,11,15]

target = 9

遍历过程：

i	nums[i]	补数	哈希表
0	2	7	存入2
1	7	2	找到2 ✔

[0,1]

五、C语言实现（哈希表）

由于 C 语言没有内置哈希表，我们可以用链地址法实现简单哈希表。

#include <stdlib.h> #define SIZE 20011 typedef struct Node { int key; int value; struct Node* next; }Node; Node* hashTable[SIZE]; int hash(int key) { if(key < 0) key = -key; return key % SIZE; } void insert(int key, int value) { int h = hash(key); Node* node = (Node*)malloc(sizeof(Node)); node->key = key; node->value = value; node->next = hashTable[h]; hashTable[h] = node; } int find(int key) { int h = hash(key); Node* cur = hashTable[h]; while(cur) { if(cur->key == key) return cur->value; cur = cur->next; } return -1; } int* twoSum(int* nums, int numsSize, int target, int* returnSize) { for(int i = 0; i < SIZE; i++) hashTable[i] = NULL; int* res = (int*)malloc(sizeof(int) * 2); for(int i = 0; i < numsSize; i++) { int complement = target - nums[i]; int index = find(complement); if(index != -1) { res[0] = index; res[1] = i; *returnSize = 2; return res; } insert(nums[i], i); } *returnSize = 0; return NULL; }