【leetcode】两数之和【简单】( 注释详解:C++map/ C哈希表)
本题为函数题,函数头固定如下:
C++:
vector<int> twoSum(vector<int>& nums, int target)
C:
int* twoSum(int* nums, int numSize, int target, int* returnSize)
下面是时间复杂度为O(n)的代码
C++AC代码:
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {vector<int>re;//存储结果和返回map<int, int>mp;//用以实现类似“字典”的功能//第一个元素存储当前nums中访问的值,第二个元素存储它的下标for(int i=0; i<nums.size(); i++)//每个数字访问且仅访问一次{auto it = mp.find(target - nums[i]);if(it != mp.end())//找到了{re.push_back(i);re.push_back(it->second);return re;}mp.insert(pair<int, int>(nums[i], i));}}
};
C详解代码(代码思路来自leetcode官方题解)
#include<bits/stdc++.h>
#include"uthash.h"
using namespace std;typedef struct{int key;//本质是要查找的对象//本题中存储nums中的值int val;//本质是key的对应信息//本题中存储key值在nums中的下标UT_hash_handle hh;
}HS;
HS* hashtable;HS* find(int ikey)
{HS* tmp;//初始化一个HS*类型准备接收结果HASH_FIND_INT(hashtable, &ikey, tmp);return tmp;
}void insert(int ikey, int ival){HS* it = find(ikey);if(!it)//若原先不存在该键{HS* tmp = (HS*)malloc(sizeof(HS));//则申请新空间,tmp->key = ikey;//赋予键值HASH_ADD_INT(hashtable, key, tmp);//插入哈西表}else{//已经存在该键it->val = ival;//直接修改键对应的值}
}int* twoSum(int* nums, int numSize, int target, int* returnSize)
{hashtable = NULL;for(int i=0; i<numSize; i++){HS* it = find(target-nums[i]);//尝试查找nums中是否存在该值if(it)//存在{int* ret = (int*)malloc(sizeof(int)* 2);//构造可容纳两个整数的数组, 作为返回值ret[0] = it->val;ret[1] = i;*returnSize = 2;return ret;//最终返回一个二元数组}//若没有找到, 则将当前nums中元素插入哈西表insert(nums[i], i);}
}
~希望对你有帮助~