有人相爱，有人夜里开车看海，有人leetcode第一题都做不出来

深藏功名丿小志 发表于 2024-12-20 20:50

本帖最后由深藏功名丿小志于 2024-12-20 21:00 编辑

# 一、引言

在日常技术探索的漫漫长路上，不经意的瞬间总能触发一段新奇旅程。就像今天，我随手点开 “LeetCode” 官网，指尖轻触 “题库”，瞬间被拉回了几年前的青涩时光 —— 我的刷题记录竟还定格在那道经典的 “两数之和”，彼时初涉力扣的青涩模样如在眼前。

心里犯起嘀咕，当年这题莫不是靠着答案才勉强通过？一股不服输的劲儿涌上心头，当下决定花两分钟重温旧题。本以为手到擒来，代码在键盘上噼里啪啦敲完，自信满满地提交，没想到换来的却是无情的 “运行错误”。

屏幕上那刺眼的提示，像极了学生时代考试失利的红灯。要是换做屏幕前的你，能一举拿下这道题吗？来吧，让我们一同深入剖析这道 “LeetCode” 必刷之 “两数之和”，看看其中暗藏哪些玄机。

# 二、问题描述

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

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

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

**示例 1**：

> 输入：nums = , target = 9
> 输出：
> 解释：因为 nums + nums == 9 ，返回

# 三、解决方案

## 3.1 暴力枚举

初涉此题，多数人脑海里蹦出的第一招便是暴力枚举。

通俗来讲，就是一股脑遍历整个数组，逐个寻觅 `target - x` 的身影。不过这里头有个小窍门，前面已经 “验过” 的元素就没必要再跟当前元素 `x` 配对了，毕竟题目限定每个元素只能用一次，所以目光只需聚焦在 `x` 后面的元素群里找 `target - x` 就行。

```c
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
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 + nums == target) {
   int* ret = malloc(sizeof(int) * 2);
   ret = i, ret = j;
   *returnSize = 2;
   return ret;
   }
}
}
*returnSize = 0;
return NULL;
}
```

时间复杂度：O(N<sup>2</sup>)，其中 N 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。

空间复杂度：O(1)。

说起来，这题对基础薄弱的小伙伴不太友好，就像我，一开始愣是没瞅见注释，把结算结果错塞到 `returnSize` 里，闹了个不大不小的笑话。

## 3.2 哈希表

仔细琢磨，暴力枚举之所以耗时，症结就在于找 `target - x` 时太 “磨蹭”，时间复杂度居高不下。那有没有 “快刀斩乱麻” 的妙招呢？哈希表应运而生，它就像一把精准导航的钥匙，能闪电般定位目标元素，把找 `target - x` 的时间复杂度从 O (N) 断崖式降至 O (1)。

```c
struct hashTable {
int key;
int val;
UT_hash_handle hh;
};

struct hashTable* hashtable;

struct hashTable* find(int ikey) {
struct hashTable* tmp;
HASH_FIND_INT(hashtable, &ikey, tmp);
return tmp;
}

void insert(int ikey, int ival) {
struct hashTable* it = find(ikey);
if (it == NULL) {
struct hashTable* tmp = malloc(sizeof(struct hashTable));
tmp->key = ikey, tmp->val = ival;
HASH_ADD_INT(hashtable, key, tmp);
} else {
it->val = ival;
}
}

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);
if (it != NULL) {
   int* ret = malloc(sizeof(int) * 2);
   ret = it->val, ret = i;
   *returnSize = 2;
   return ret;
}
insert(nums, i);
}
*returnSize = 0;
return NULL;
}
```

在第一层循环里面，先去哈希表中查找是否有 key 为 `target - nums`的值，如果查到了就分配一片空间并将计算结果返回，反之就将键值对 `nums, i`插入哈希表中。

为了让大伙理解更透彻，特意奉上一张官方视频讲解中的配图（见下图），图文并茂，一目了然。

!(data/attachment/forum/202412/20/204814pq0fdc0izdqd3g0d.png "001-hash-map.png")

顺带提一嘴，后面章节会详细拆解 UT_hash_handle 以及 HASH 函数，这里先卖个小关子。

时间复杂度：O(N)，其中 N 是数组中的元素数量。对于每一个元素 x，我们可以 O(1) 地寻找 target - x。

空间复杂度：O(N)，其中 N 是数组中的元素数量。主要为哈希表的开销。

值得留意的是，官方解法也并非十全十美，像 `struct hashTable* hashtable` 定义哈希表时忘了初始化指针，这可是个暗藏隐患的 “雷区”。uthash 作者再三强调，此处务必初始化为 NULL。

!(data/attachment/forum/202412/20/204837e3tzlaallaw4c3ai.png "002-Declare the hash.png")

大伙日常写代码可得长点心，野指针这玩意儿，一旦冒头，那就是程序崩溃的 “定时炸*”。

# 四、网友锐评

这道题一抛出，网友们的吐槽那叫一个热闹非凡，让我们来看一下吧。

有人相爱，有人夜里开车看海，有人leetcode第一题都做不出来。

哈希表是什么、我连两个for都想了很久，你给我说哈希表。

别跟我谈什么空间复杂度，时间复杂度，我解题就是一手暴力枚举，自信提交，运行错误。

是谁力扣第一题都做的磕磕巴巴，原来是我。

看题之前我是心高气傲，看题之后我是生死难料。

单纯c语言角度看，这题用c 比用其他语言要麻烦，因为一上来就涉及到了最麻烦的指针。

# 五、知识点扩展

哈希表，你太让我陌生了。

我开发到现在也没用到哈希算法。

今天咱就抱着学习的态度来学习一下哈希表。

## 5.1 哈希表

哈希表是一种高效的数据结构，它通过哈希函数将键（Key）映射到表中的位置，从而实现快速查找、插入和删除操作。

`哈希函数将键转换为数组索引，使得每个元素都能直接定位到其存储位置`，理想情况下，这种映射关系使得查找、插入和删除操作的时间复杂度接近 O(1)。

## 5.2 UT_hash_handle

在使用哈希表求解时，结构体中使用了一个 `UT_hash_handle`类型，这个类型是什么？在哪里？

C语言的标准库中没有哈希表的函数可以使用，需要包含第三方头文件uthash.h，第三方库链接放到最后了。

`UT_hash_handle`类型在 `uthash.h`头文件定义如下，通过其中的成员看出是通过双向链表实现哈希表的。

```c
typedef struct UT_hash_handle {
struct UT_hash_table *tbl;
void *prev;                   /* prev element in app order    */
void *next;                   /* next element in app order    */
struct UT_hash_handle *hh_prev; /* previous hh in bucket order */
struct UT_hash_handle *hh_next; /* next hh in bucket order    */
const void *key;                /* ptr to enclosing struct's key*/
unsigned keylen;                /* enclosing struct's key len */
unsigned hashv;                /* result of hash-fcn(key)    */
} UT_hash_handle;
```

# 六、uthash

## 6.1 uthash 简介

uthash 是一款极为精巧的工具，代码量仅约 1000 行 C 代码。它借助宏的形式巧妙实现，进而天然具备内联特性。它对哈希表项目的操作提供了完备支持，在功能层面，支持如下操作。

1. add/replace
2. find
3. delete
4. count
5. iterate
6. sort

## 6.2 uthash 例程

```c
#include <stdio.h> /* printf */
#include <stdlib.h>/* atoi, malloc */
#include <string.h>/* strcpy */
#include "uthash.h"

struct my_struct {
int id;                /* key */
char name;
UT_hash_handle hh;       /* makes this structure hashable */
};

struct my_struct *users = NULL; /* important! initialize to NULL */

void add_user(int user_id, const char *name) {
struct my_struct *s;

HASH_FIND_INT(users, &user_id, s);/* id already in the hash? */
if (s == NULL) {
s = (struct my_struct*)malloc(sizeof *s);
s->id = user_id;
HASH_ADD_INT(users, id, s);/* id is the key field */
}
strcpy(s->name, name);
}

struct my_struct *find_user(int user_id) {
struct my_struct *s;

HASH_FIND_INT(users, &user_id, s);/* s: output pointer */
return s;
}

void delete_user(struct my_struct *user) {
HASH_DEL(users, user);/* user: pointer to deletee */
free(user);
}

void delete_all() {
struct my_struct *current_user;
struct my_struct *tmp;

HASH_ITER(hh, users, current_user, tmp) {
HASH_DEL(users, current_user);/* delete it (users advances to next) */
free(current_user);          /* free it */
}
}

void print_users() {
struct my_struct *s;

for (s = users; s != NULL; s = (struct my_struct*)(s->hh.next)) {
printf("user id %d: name %s\n", s->id, s->name);
}
}

int by_name(const struct my_struct *a, const struct my_struct *b) {
return strcmp(a->name, b->name);
}

int by_id(const struct my_struct *a, const struct my_struct *b) {
return (a->id - b->id);
}

const char *getl(const char *prompt) {
static char buf;
char *p;
printf("%s? ", prompt); fflush(stdout);
p = fgets(buf, sizeof(buf), stdin);
if (p == NULL || (p = strchr(buf, '\n')) == NULL) {
puts("Invalid input!");
exit(EXIT_FAILURE);
}
*p = '\0';
return buf;
}

int main() {
int id = 1;
int running = 1;
struct my_struct *s;
int temp;

while (running) {
printf(" 1. add user\n");
printf(" 2. add or rename user by id\n");
printf(" 3. find user\n");
printf(" 4. delete user\n");
printf(" 5. delete all users\n");
printf(" 6. sort items by name\n");
printf(" 7. sort items by id\n");
printf(" 8. print users\n");
printf(" 9. count users\n");
printf("10. quit\n");
switch (atoi(getl("Command"))) {
   case 1:
   add_user(id++, getl("Name (20 char max)"));
   break;
   case 2:
   temp = atoi(getl("ID"));
   add_user(temp, getl("Name (20 char max)"));
   break;
   case 3:
   s = find_user(atoi(getl("ID to find")));
   printf("user: %s\n", s ? s->name : "unknown");
   break;
   case 4:
   s = find_user(atoi(getl("ID to delete")));
   if (s) {
      delete_user(s);
   } else {
      printf("id unknown\n");
   }
   break;
   case 5:
   delete_all();
   break;
   case 6:
   HASH_SORT(users, by_name);
   break;
   case 7:
   HASH_SORT(users, by_id);
   break;
   case 8:
   print_users();
   break;
   case 9:
   temp = HASH_COUNT(users);
   printf("there are %d users\n", temp);
   break;
   case 10:
   running = 0;
   break;
}
}

delete_all();/* free any structures */
return 0;
}
```

# 七、链接

* `https://leetcode.cn/problems/two-sum/solutions/434597/liang-shu-zhi-he-by-leetcode-solution/`
* `https://github.com/troydhanson/uthash`
* `https://troydhanson.github.io/uthash/userguide.html`

# 八、最后

在日常的开发工作里，大家有没有像我这般，基本就靠着 `if、switch、for` 这些基础语句结构一路 **“闯荡江湖”**，很少主动去调用那些精妙复杂的算法呢？

真挺好奇的，评论区留下你的答案。

[!(/source/plugin/zhanmishu_markdown/template/editor/images/upload.svg) 附件：uthash.rar](forum.php?mod=attachment&aid=2338722 "attachment")

goyhuan 发表于 2024-12-25 09:56

不错鼓励知识变现

深藏功名丿小志 发表于 2024-12-25 10:20

goyhuan 发表于 2024-12-25 09:56
不错鼓励知识变现

哈哈，你也赶紧参与进来吧{:lol:}

电子烂人 发表于 2024-12-25 10:24

太经典了，多少leetcode小白死在两数之和上

深藏功名丿小志 发表于 2024-12-25 14:38

电子烂人发表于 2024-12-25 10:24
太经典了，多少leetcode小白死在两数之和上

关键有些小白都不知道怎么死的...{:lol:}

abner_ma 发表于 2024-12-28 11:21

哪有这么啰嗦：#include <stdio.h>

// 函数声明
void twoSum(int nums[], int size, int target);

int main() {
// 示例数组和目标值
int nums[] = {2, 7, 11, 15};
int size = sizeof(nums) / sizeof(nums);
int target = 9;

// 调用函数查找两数之和等于目标值的索引
twoSum(nums, size, target);

return 0;
}

void twoSum(int nums[], int size, int target) {
int i, j;
for (i = 0; i < size - 1; ++i) {
   for (j = i + 1; j < size; ++j) {
         if (nums + nums == target) {
            printf("Indices: %d, %d\n", i, j);
            return;
         }
   }
}
// 如果没有找到这样的两个数，则输出提示信息
printf("No two sum solution found.\n");
}python
def two_sum(nums, target):
# 创建一个空字典用于存储数值及其索引
num_dict = {}

# 遍历数组中的每个元素及其索引
for i, num in enumerate(nums):
   # 计算需要找到的另一个数
   complement = target - num

   # 检查这个数是否已经在字典中
   if complement in num_dict:
         # 如果找到了，返回这两个数的索引
         return , i]

   # 将当前数及其索引加入到字典中
   num_dict = i

# 如果没有找到这样的两个数，则返回空列表或其他表示未找到的标志
return []

# 示例用法：
nums =
target = 9
print(two_sum(nums, target))# 输出:

瞎折腾 发表于 2024-12-28 14:33

abner_ma 发表于 2024-12-28 11:21
哪有这么啰嗦：python

经典啊

深藏功名丿小志 发表于 2025-1-2 17:22

abner_ma 发表于 2024-12-28 11:21
哪有这么啰嗦：python

C中少了一次循环，优化了{:lol:}

海市蜃楼神秘 发表于 2025-2-28 17:29

特意看了一下，我的LeetCode第一道还没过去呢

深藏功名丿小志 发表于 2025-2-28 20:53

海市蜃楼神秘发表于 2025-2-28 17:29
特意看了一下，我的LeetCode第一道还没过去呢

刚过了第二题，过了这个劲就不想看了，后面太难了，坚持不下去。你加油...

海市蜃楼神秘 发表于 2025-2-28 20:59

深藏功名丿小志发表于 2025-2-28 20:53
刚过了第二题，过了这个劲就不想看了，后面太难了，坚持不下去。你加油... ...

哈哈，这感觉我太懂了！这可太正常啦。调整一下状态，等精力充沛了再继续冲。

页: [1]

21ic电子技术开发论坛's Archiver

有人相爱，有人夜里开车看海，有人leetcode第一题都做不出来