1.两数之和-LeetCode

• C语言
• C++

算法思想：在遍历的过程中利用哈希表记录已经存在的数据，每次遍历到一个新的元素a，都向前寻找target-a这个元素是否存在（利用哈希表，从而避免了二重循环遍历查找target-a），由此将时间复杂度降低到O(n)。当然随之而来付出的代价即是空间复杂度增加。

C语言

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

struct HashTable{
    int _key;
    int _val;
    UT_hash_handle hh;
};
struct HashTable *hash_table = NULL;

struct HashTable *find(int ikey){
    struct HashTable *tmp;
    HASH_FIND_INT(hash_table, &ikey, tmp);
    return tmp;
}

void insert(int ikey, int ival){
    struct HashTable *it = find(ikey);
    if (it == NULL){
        struct HashTable *tmp = malloc(sizeof(struct HashTable));
        tmp -> _key = ikey;
        tmp -> _val = ival;
        HASH_ADD_INT(hash_table, _key, tmp);
    }else{
        it -> _val = ival;
    }
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    hash_table = NULL;
    for(size_t i = 0; i < numsSize; ++i){
        struct HashTable *it = find(target - nums[i]);
        if(it != NULL){
            int *ret = malloc(sizeof(int)*2);
            ret[0] = it ->_val;
            ret[1] = i;
            *returnSize = 2;
            return ret;
        }else{
            insert(nums[i], i);
        }
    }
    *returnSize = 0;
    return NULL;
}

C++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> hashtable;
        int len = nums.size();
        for(int i = 0; i < len; ++i){
            auto it = hashtable.find(target - nums[i]);
            if(it != hashtable.end()){
                return {it -> second, i};
            }else{
                hashtable[nums[i]] = i;
            }
        }
        return {};
    }
};