從零開始刷力扣（bushi

題目放在這：

給定一個整數(shù)數(shù)組?nums?和一個整數(shù)目標(biāo)值?target，請你在該數(shù)組中找出和為目標(biāo)值target的兩個整數(shù)，并返回它們的數(shù)組下標(biāo)。

你可以假設(shè)每種輸入只會對應(yīng)一個答案。但是，數(shù)組中同一個元素在答案里不能重復(fù)出現(xiàn)。

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

示例?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]

提示：

2?<=?nums.length?<=?104
-109?<=?nums[i]?<=?109
-109?<=?target?<=?109

只會存在一個有效答案

放一個分割線在這：

---

我自己也是C語言復(fù)建，沒有系統(tǒng)學(xué)習(xí)過數(shù)據(jù)結(jié)構(gòu)，所以第一反應(yīng)真就是暴力破解（見笑了）

也就是依次將數(shù)組的兩個元素相加，和目標(biāo)數(shù)做對比

因為只有一個有效答案，那么就可以在檢索到和等于目標(biāo)數(shù)數(shù)，直接輸出對應(yīng)的坐標(biāo)

如果遍歷結(jié)束沒有得到結(jié)果，則輸出NULL

借一下leecode的標(biāo)準(zhǔn)答案，這邊我自己加上了前期的輸入輸出語句，這樣方便看到結(jié)果：

#include <stdio.h>
#include <stdlib.h>int *twoSum(int *nums, int numsSize, int target, int *returnSize);int main() {int *p, *returnSize;int nums[10];int numsSize = 0, target = 0;*returnSize = 2;printf("找出數(shù)組中和為目標(biāo)數(shù)的兩個元素的下標(biāo)：\n請輸入數(shù)組的長度（不超過十）\n");scanf("%d", &numsSize);printf("請輸入數(shù)組的內(nèi)容，并用回車分隔\n");for (int i = 0; i < numsSize; i++) {scanf("%d", &nums[i]);}printf("您輸入的數(shù)組內(nèi)容為：nums[]=");for (int i = 0; i < numsSize; i++) {printf("%d ", nums[i]);}printf("請輸入您的目標(biāo)數(shù)：\n");scanf("%d", &target);p = twoSum(nums, numsSize, target, returnSize);if (p != NULL) {printf("您的目標(biāo)數(shù)對應(yīng)的坐標(biāo)下標(biāo)為：");printf("%d ", p[0]);printf("%d", p[1]);} elseprintf("您的目標(biāo)數(shù)不能被數(shù)組中的任何兩個數(shù)相加得到。");return 0;
}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 *ret = (int *)malloc(sizeof(int) * 2);ret[0] = i, ret[1] = j;*returnSize = 2;return ret;}}}*returnSize = 0;return NULL;
}

?簡單講一點：

1、<stdio.h>頭文件，翻譯為standard input output

程序中用到的scanf、printf，都需要使用標(biāo)準(zhǔn)的輸入輸出庫

2、<stdlib.h>頭文件，和存儲、空間分配密切相關(guān)的一個函數(shù)

程序中用到的malloc函數(shù)，用來分配內(nèi)存空間，出自于這個頭文件

類似的還有calloc、free、realloc函數(shù)等，感興趣的可以看一看

3、malloc函數(shù)：

函數(shù)原型：void * malloc(unsigned size);

功能是分配size字節(jié)的存儲區(qū)。程序中需要兩個int的空間所以乘2

默認的類型是void*，由于我設(shè)定了ret為int*類型，所以這里強制類型轉(zhuǎn)換為int*

（leecode標(biāo)準(zhǔn)答案是沒有這個強制轉(zhuǎn)換的，其實我也有印象這一步可以自動轉(zhuǎn)換，但是我用的Dev C++報錯）

再放一個分割線：

---

那么肯定不可能就到此為止了，在今年校招（2024屆校招）中，不知道大家有沒有關(guān)注騰訊的招聘，直播間提到的就是這個問題。

不過大佬顯然指的是用哈希表

什么是哈希表？

哈希表是一種數(shù)據(jù)結(jié)構(gòu)，提供了快速的插入操作和查找操作

不管哈希表有多少數(shù)據(jù)，插入和查找的時間復(fù)雜度都是O（1），查找速度非?？?/p>

不過，哈希表基于數(shù)組，一旦數(shù)組被填滿，性能就大不如前。

關(guān)于哈希表，推薦一個視頻：

『教程』哈希表是個啥？_嗶哩嗶哩_bilibilihttps://www.bilibili.com/video/BV1qR4y1V7g6/?spm_id_from=333.337.search-card.all.click&vd_source=86629babf8e8eb6ebc7b7475ab3f61a2簡單理解為：用時間換空間

先放代碼（后面有詳細解釋，這里方便想自學(xué)的大佬）：

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

然后咱們就來詳細解釋這個代碼。

已知，用哈希表查詢，首先將要查找的東西作為參數(shù)進入一個函數(shù)，得到一個確定的數(shù)字

該數(shù)字就是哈希表中，查詢結(jié)果的地址。

這樣，本來我們需要一個個查詢、比較的，現(xiàn)在只需要經(jīng)過一次函數(shù)計算，一次查找。

將目光回到代碼上：

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

給出哈希表的結(jié)構(gòu)，這個在哈希表的使用中是確定的，一般第一個是數(shù)值，第二個是位置（原本數(shù)組中的位置），第三個是一個句柄，鏈接前一個和后一個哈希表?

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

建立一個哈希表的指針，并且設(shè)置一個尋找函數(shù)

輸入?yún)?shù)是我們要找的結(jié)果，并內(nèi)置了HASH_FIND_INT函數(shù)

這個是頭文件中包含的函數(shù)，主要參數(shù)有三個，

第一個就當(dāng)默認參數(shù)，第二個是要找的值，第三個是哈希表的指針（做返回值用）

該函數(shù)的意義是：

找到ikey對應(yīng)的值，如果哈希表中沒有，tmp=NULL

如果找到了對應(yīng)的值，tmp的第一個值為ikey，第二個是ikey對應(yīng)的哈希表的val

簡單來說就是一個查詢操作，如果沒有返回NULL，如果有返回對應(yīng)的數(shù)值和位置

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;}
}

定義一個插入函數(shù)

find函數(shù)就是我們上面提到的尋找函數(shù)，會返回一個哈希表的指針，

如果返回的指針為NULL，也就是哈希表中沒有我們要找的值，會再次定義一個分配了一個哈希表空間的指針tmp，并將對應(yīng)的數(shù)值，以及數(shù)值在原本數(shù)組中的數(shù)值賦值給新建的哈希表

運用HASH_ADD_INT函數(shù)將這個新建的數(shù)據(jù)增加到哈希表中

如果返回的指針有數(shù)值，也就是哈希表中已經(jīng)存在對應(yīng)的結(jié)果了，找到了，那就更方便，直接記錄

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

這是函數(shù)的主體

按照原始數(shù)組的順序循環(huán)，依次查找target-nums[i]的結(jié)果，剛開始都是向哈希表內(nèi)添加數(shù)，直到找到對應(yīng)的結(jié)果

因為這里假設(shè)只存在唯一解，所以就沒有必要考慮多種情況

簡單畫一個執(zhí)行的邏輯吧：
?

?