代码随想录一刷——1.两数之和

当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。

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;

}