1. 題目描述
給定一個整數數組 nums 和一個目標值 target，請你在該數組中找出和為目標值的那 兩個 整數，并返回他們的數組下標。
你可以假設每種輸入只會對應一個答案。但是，數組中同一個元素不能使用兩遍。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
2. 解法分析
2.1 解法1：雙循環
容易想到使用雙層for循環來枚舉答案的暴力方法解決此問題，但是效率太低下，O(n2)時間復雜度，不適合大數據量
該方法過程如下：
- 構建循環
-
外層循環變量
i從0到numsSize-1 -
內層循環變量
j從i+1到numsSize-1（確保不會重復使用同一個元素）
- 檢查數對和:
if(nums[i] + nums[j] == target)-
如果找到滿足條件的數對，執行以下操作：
-
設置返回大小
*returnSize = 2 -
動態分配結果數組（兩個int）
-
將兩個索引存入數組：
result[0]=i,result[1]=j -
直接返回結果數組
- 未找到解的處理:
-
設置
*returnSize = 0 -
返回
NULL
時間復雜度
- O(n2): 最壞情況下需要檢查所有n(n-1)/2個數對
空間復雜度
- O(1): 除結果數組外只使用常數空間（結果數組不計入空間復雜度時）
- 無解處理:
-
設置
*returnSize=0并返回NULL是標準做法 -
調用者可通過
returnSize判斷是否有解
示例執行過程
輸入：nums = [2,7,11,15], target=9
-
i=0(值2),j=1(值7): 2+7=9 → 找到解 -
分配結果數組，設置
result[0]=0,result[1]=1 -
設置
*returnSize=2 -
返回結果數組
[0,1]
2.2 解法二：哈希表
當我們需要查詢一個元素是否出現過，或者一個元素是否在集合里的時候，就要第一時間想到哈希法。我們首先將所有元素遍歷一遍存放到哈希表中，第二次遍歷的時候就去哈希表中查詢是否有已經遍歷過的數和當前遍歷的數相加是否等于target。
哈希表版本解題思路：
步驟1：定義哈希表結構
-
使用結構體
map構造哈希表的條目，包含：key: 數組元素的值value: 該元素在數組中的索引
步驟2：實現哈希表基本操作
-
hashMapAdd: 添加或更新鍵值對。如果鍵不存在，創建新條目并添加到哈希表；如果存在，則更新其值。 -
hashMapFind: 根據鍵查找條目，返回條目指針（找不到返回NULL）。 -
hashMapCleanUp: 清理哈希表，釋放所有條目內存。
步驟3：實現twoSum函數
a. 初始化全局哈希表指針為NULL（避免之前的數據干擾）。
b. 預分配結果數組ans（兩個整數）。
c. 第一次遍歷數組：將每個元素的值作為key，索引作為value存入哈希表。
注意：如果遇到相同的元素，后面的索引會覆蓋前面的（因為同一個key在哈希表中只能存在一個）。
d. 第二次遍歷數組：對于每個元素nums[i]，計算補數complement = target - nums[i]，然后在哈希表中查找補數。
查找成功且滿足條件（補數對應的索引不等于當前索引，避免同一個元素用兩次）時：
將當前索引i和補數的索引hashMapRes->value存入結果數組。
設置返回數組大小為2，返回結果數組。
e. 如果遍歷結束未找到，則清理哈希表并返回NULL。
優勢：
哈希表版本的核心思路是“空間換時間”，通過O(n)的額外空間將時間復雜度從O(n2)降低到O(n)。它通過兩次遍歷完成：
第一次遍歷：建立值到索引的映射（哈希表）。
第二次遍歷：對于每個元素，檢查其補數是否在哈希表中（且不是自身）。
與雙層循環法相比，哈希表法更適合處理大規模數據，但需要注意內存泄漏和線程安全問題。
3. C語言代碼實現
3.1 雙層for循環法
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){*returnSize = 2;int* result = (int*)malloc(2 * sizeof(int));result[0] = i;result[1] = j;return result;}}}*returnSize = 0;return NULL;
}
3.2 哈希表法
typedef struct
{int key;int value;UT_hash_handle hh;
}map;map* hashMap = NULL;void hashMapAdd(int key, int value){map* s;//檢查key是否在hash表中HASH_FIND_INT(hashMap, &key, s);if(s == NULL){s = (map*)malloc(sizeof(map));s->key = key;HASH_ADD_INT(hashMap, key, s);}s->value = value;
}map* hashMapFind(int key){map* s;HASH_FIND_INT(hashMap, &key, s);return s;
}void hashMapCleanUp(){map* cur, *tmp;HASH_ITER(hh, hashMap, cur, tmp){HASH_DEL(hashMap, cur);free(cur);}
}void hashPrint(){map* s;for(s = hashMap; s != NULL; s = (map*)(s -> hh.next)){printf("key = %d, value = %d", s->key, s->value);}
}int* twoSum(int* nums, int numsSize, int target, int* returnSize){int i, *ans;//在哈希表里尋找補數map* hashMapRes;hashMap = NULL;ans = malloc(sizeof(int) * 2);for(i = 0; i < numsSize; i++){//key代表nums[i]的值，value代表所在indexhashMapAdd(nums[i], i);}for(i = 0; i < numsSize; i++){hashMapRes = hashMapFind(target - nums[i]);if(hashMapRes && hashMapRes -> value != i){ans[0] = i;ans[1] = hashMapRes -> value;*returnSize = 2;return ans;}}hashMapCleanUp();return NULL;
}
