企业官网建设流程全解析

题目

给定一个整数数组 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 为例：

1. 初始化哈希表为空。
2. 遍历到 i = 0，nums[0] = 2，complement = 9 - 2 = 7，哈希表中没有 7，将 (2, 0) 存入哈希表。
3. 遍历到 i = 1，nums[1] = 7，complement = 9 - 7 = 2，在哈希表中找到键 2，对应下标 0，返回 [0, 1]。
   复杂度
   1. 时间复杂度：O(n)
      遍历数组一次，每个元素在哈希表中的查找和插入平均为 O(1)，因此总时间为O(n)。
   2. 空间复杂度：O(n)
      哈希表最多存储 n 个元素，需要 O(n) 的额外空间。

Code

#include<stdlib.h>#include<limits.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，减少冲突inthashSize=numsSize*2+1;HashNode*hash=(HashNode*)malloc(sizeof(HashNode)*hashSize);if(!hash){*returnSize=0;returnNULL;}// 初始化哈希表，所有位置标记为空for(inti=0;i<hashSize;i++){hash[i].key=EMPTY;hash[i].val=-1;}int*result=(int*)malloc(sizeof(int)*2);if(!result){free(hash);*returnSize=0;returnNULL;}for(inti=0;i<numsSize;i++){intcomplement=target-nums[i];// 计算 complement 的哈希位置（处理负数）intindex=((complement%hashSize)+hashSize)%hashSize;// 线性探测查找 complementwhile(hash[index].key!=EMPTY){if(hash[index].key==complement){// 找到了配对的数，返回两个下标result[0]=hash[index].val;result[1]=i;*returnSize=2;free(hash);returnresult;}index=(index+1)%hashSize;}// 哈希表中没有 complement，将当前元素插入哈希表intpos=((nums[i]%hashSize)+hashSize)%hashSize;while(hash[pos].key!=EMPTY){pos=(pos+1)%hashSize;}hash[pos].key=nums[i];hash[pos].val=i;}// 理论上不会执行到这里，因为题目保证有解free(hash);free(result);*returnSize=0;returnNULL;}

作者：一清风月一流年
链接：https://leetcode.cn/problems/two-sum/solutions/4039193/1-liang-shu-zhi-he-by-yi-qing-feng-yue-y-g935/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。