当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。
C++：
unordered_map
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target)
{
unordered_map<int,int> m;
for(int i = 0;i<nums.size();i++)
{
int s = target-nums[i];
auto iter = m.find(s);
if(iter!=m.end())
{
return {iter->second,i};
}
m.insert(pair<int,int>(nums[i],i));
}
return {};
}
};
Python:
字典
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
result = dict()
for index,value in enumerate(nums):
if target-value in result:
return [result[target-value],index]
result[value] = index
return []
集合
result = set()
for index,value in enumerate(nums):
if target-value in result:
return [nums.index(target-value),index]
result.add(value)
return []
C：
hashtable
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
typedef struct {
int key;
int value;
UT_hash_handle hh; // make this structure hashable
} map;
map* hashMap = NULL;
void hashMapAdd(int key, int value){
map* s;
// key already in the 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;
// *s: output pointer
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);
}
}
int* twoSum(int* nums, int numsSize, int target, int* returnSize)
{
hashMap = NULL;
map* hashMapres;
int *ans;
ans = (int*)malloc(sizeof(int)*2);
for(int i=0;i<numsSize;i++)
{
hashMapAdd(nums[i],i);
}
for(int 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;
}
