题目给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。你可以假设每种输入只会对应一个答案并且你不能使用两次相同的元素。你可以按任意顺序返回答案。示例 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只会存在一个有效答案进阶你可以想出一个时间复杂度小于 O(n2) 的算法吗思路最直观的暴力解法是双重循环枚举所有两数组合时间复杂度 O(n2)。进阶要求时间复杂度小于 O(n2)可以使用哈希表将查找时间降到 O(1)。具体做法1. 遍历数组 nums对于当前元素 nums[i]计算它需要的配对值 complement target - nums[i]。2. 在哈希表中查找 complement 是否存在(1). 如果存在说明之前已经遍历过一个数它与当前数之和为 target直接返回这两个数的下标。(2). 如果不存在将当前元素 nums[i] 和它的下标 i 存入哈希表继续遍历。3. 因为题目保证有且仅有一个有效答案所以一定能在遍历过程中找到。由于 C 语言没有内置哈希表我们需要手写一个简单的哈希表。这里使用开放寻址法线性探测用数组存储键值对。解题过程以 nums [2, 7, 11, 15], target 9 为例初始化哈希表为空。遍历到 i 0nums[0] 2complement 9 - 2 7哈希表中没有 7将 (2, 0) 存入哈希表。遍历到 i 1nums[1] 7complement 9 - 7 2在哈希表中找到键 2对应下标 0返回 [0, 1]。复杂度时间复杂度O(n)遍历数组一次每个元素在哈希表中的查找和插入平均为 O(1)因此总时间为O(n)。空间复杂度O(n)哈希表最多存储 n 个元素需要 O(n) 的额外空间。Code#includestdlib.h#includelimits.h// 哈希表节点存储键数值和值下标typedefstruct{intkey;intval;}HashNode;// 用 INT_MIN 表示哈希表位置为空#defineEMPTYINT_MIN/** * 两数之和哈希表法 * * param nums 整数数组 * param numsSize 数组长度 * param target 目标值 * param returnSize 返回数组的长度固定为 2 * return 返回两个下标组成的数组若未找到返回 NULL */int*twoSum(int*nums,intnumsSize,inttarget,int*returnSize){// 哈希表大小取 2 * numsSize保证装载因子小于 0.5减少冲突inthashSizenumsSize*21;HashNode*hash(HashNode*)malloc(sizeof(HashNode)*hashSize);if(!hash){*returnSize0;returnNULL;}// 初始化哈希表所有位置标记为空for(inti0;ihashSize;i){hash[i].keyEMPTY;hash[i].val-1;}int*result(int*)malloc(sizeof(int)*2);if(!result){free(hash);*returnSize0;returnNULL;}for(inti0;inumsSize;i){intcomplementtarget-nums[i];// 计算 complement 的哈希位置处理负数intindex((complement%hashSize)hashSize)%hashSize;// 线性探测查找 complementwhile(hash[index].key!EMPTY){if(hash[index].keycomplement){// 找到了配对的数返回两个下标result[0]hash[index].val;result[1]i;*returnSize2;free(hash);returnresult;}index(index1)%hashSize;}// 哈希表中没有 complement将当前元素插入哈希表intpos((nums[i]%hashSize)hashSize)%hashSize;while(hash[pos].key!EMPTY){pos(pos1)%hashSize;}hash[pos].keynums[i];hash[pos].vali;}// 理论上不会执行到这里因为题目保证有解free(hash);free(result);*returnSize0;returnNULL;}作者一清风月一流年链接https://leetcode.cn/problems/two-sum/solutions/4039193/1-liang-shu-zhi-he-by-yi-qing-feng-yue-y-g935/来源力扣LeetCode著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。