1, Foreword

Please take care of me for the first time. Hello, everyone. I'm Sanshui, a junior reading algorithm Xiaobai. Today is the fourth day I brush leetcode algorithm! This is the first time I have published my article on the platform. In the future, I will continue to share some humble opinions and knowledge in the process of learning algorithms on the platform. I hope you will make more corrections

2, Add two numbers

Today, let's do the arithmetic problem of adding two numbers. Let's talk about it from the two parts of understanding the meaning of the problem and solving the problem. Last question!!!

1. Meaning

Given an integer array nums and an integer target value target, please find the two integers with and as the target value target in the array and return their array subscripts.

You can assume that each input will correspond to only one answer. However, the same element in the array cannot be repeated in the answer.

You can return answers in any order.

2. Examples

Input:
nums = [2,7,11,15], target = 9
Output:
[0,1]
Explanation:
Because num [0] + num [1] = = 9, return [0, 1].

3. Topic analysis

First analyze the key points of the topic:
There are two kinds of clear output results. You must see them clearly here! The same element in the array cannot be repeated in the answer, so if violent enumeration is used, we must start with i+1 in the second for loop

① If the sum of two integers with different subscripts in the array can be found as target, the array subscripts of the two integers will be returned;
② Otherwise, null

Next, let me tell you what I thought when I first saw this problem. Ha ha, it must be solved by violent enumeration as soon as I came up (novice Xiaobai goes online)
C language code implementation:

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    for(int i = 0; i < numsSize; i++)
    {
        for(int j = i + 1; j < numsSize; j++)
        {
            if(nums[i] + nums[j] == target)
            {
                int* ret = malloc(sizeof(int) * 2);
                ret[0] = i;
                ret[1] = j;
                *returnSize = 2;
                return ret;
            }
        }
    }
    *returnSize = 0;
    return NULL;
}

python code implementation:

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        n = len(nums)
        for i in range(n):
           for j in range(i + 1, n):
               if nums[i] + nums[j] == target:
                   return [i, j]
        return []

4. Official explanation

The official solution provides two algorithmic ideas: violent enumeration; Hashtable
Next, I will focus on the analysis of the idea and code of using hash table algorithm to solve the official problem:

Train of thought analysis

Advantages of hash table algorithm:

With the increase of the amount of data, the search speed of the violent enumeration method will slow down to varying degrees. The time complexity of the algorithm is related to the number of comparisons. The time complexity of the violent enumeration method is O(n^2). The hash table is used to find whether there are target elements in the array, and the index is directly found through the elements, so the time complexity will be reduced to O(1), Its main idea is to realize fast random storage by associating the value with its storage location.

Ideas and algorithms:

We can create a hash table. For each x, we first query whether there is target-x in the hash table, and then insert x into the hash table to ensure that X does not match itself (avoid using the same element twice)

code analysis

C language code implementation and detailed notes:

//Custom data structure
struct hashTable {
    int key;//key
    int val;//value
    UT_hash_handle hh;//① Enables custom data structures to be hashed
};

struct hashTable* hashtable;//Define the hash table pointer, which is the pointer of the previous custom data structure
//Find nodes according to key value
struct hashTable* find(int ikey) {
    struct hashTable* tmp;//Defines the hashTable structure pointer variable tmp
    HASH_FIND_INT(hashtable, &ikey, tmp);//② Find the hash structure corresponding to ikey
    return tmp;
}

void insert(int ikey, int ival) {
    struct hashTable* it = find(ikey);//Returns the node it corresponding to the ikey value
    if (it == NULL) {//If not found, add
        struct hashTable* tmp = malloc(sizeof(struct hashTable));//③ Request memory space for tmp
        tmp->key = ikey, tmp->val = ival;//Point the value of the structure variable tmp to ikey and the key to ival
        HASH_ADD_INT(hashtable, key, tmp);//④ Add element to hashtable
    } else {//If found, replace
        it->val = ival;//Replace the value point in it with ival
    }
}
//Two number addition function implementation function
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    hashtable = NULL;//Initialization hashtable is null
    for (int i = 0; i < numsSize; i++) {
        struct hashTable* it = find(target - nums[i]);//Find the node corresponding to key = target - num [i]
        //⑤ if... else... The internal logical relationship is not fully understood
        if (it != NULL) {//If found
            int* ret = malloc(sizeof(int) * 2);//Apply for space for ret
            ret[0] = it->val, ret[1] = i;//ret[0] is the element subscript corresponding to target num [i], and ret[1] is the element subscript corresponding to num [i]
            *returnSize = 2;//Set the length of the returned array to 2
            return ret;//Returns the subscript of two elements
        }
        insert(nums[i], i);//If not found, insert num [i] into the hash table
    }
    *returnSize = 0;//If no matching element is found in the hash table after traversal, set the length of the returned array to 0
    return NULL;//Return null
}

python code implementation and detailed notes:

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        hashtable = dict()#Create an empty dictionary hashtable
        for i, num in enumerate(nums):#Unpack the sequence and traverse the index value and the corresponding element value
            if target - num in hashtable:#If target num exists in the key value of the dictionary
                return [hashtable[target - num], i]#Returns the subscript corresponding to two elements
            hashtable[nums[i]] = i#If target num [i] does not exist in the key value of hashtable dictionary, add num [i]: I to hashtable dictionary
        return []#After the traversal is completed, the corresponding two elements are still not found in the dictionary. If the sum of the two elements is target, null is returned

3, Analysis of key and difficult points

1. Define ut in user-defined structure_ hash_ Role of handle type variable

(1) uthash is a hash table implementation of C language. It implements hash table in the way of macro definition, which not only speeds up the running speed, but also has nothing to do with key types. uthash is also very convenient to use. You only need to include the header file uthash.h.
(2)UT_hash_handle is a structure that user-defined data must contain. Each user-defined node must contain a UT_hash_handle hh.
(3)UT_hash_handle hh: hh is a hash handle used internally. During use, you only need to define a ut in the custom structure_ hash_ A variable of handle type is enough. The name of the variable name can be taken arbitrarily, but we usually use hh (knock on the blackboard: you do not need to assign a value to the handle variable, but you must define the variable in the structure)

2. Precautions for malloc() applying for memory space

(1) malloc() can be used to dynamically allocate memory space. There is a parameter in malloc(size_t size) function, that is, the size of memory space to be allocated.
(2) The default type of malloc() is (void *), (void *) indicates that the returned pointer type is unknown, rather than no return value or null pointer. Any type of pointer can be converted to (void *), but it's best to cast it to be safe.
(3) malloc() is only responsible for opening up space and cannot initialize the allocated memory space. After dynamically allocating memory, the data in it is random garbage data.
(4) The return value of malloc() is an object.
(5) After applying for memory space, you must check whether the allocation is successful. When you no longer need the requested memory space, remember to use free() to release it. In addition, after releasing, you should point the pointer to this memory to NULL to prevent it from being accidentally used by the program later.
(6) The difference between malloc() and calloc():
① Initialize memory space: malloc() is only responsible for opening up space, and calloc() initializes the opened space to 0
② Number of parameters: malloc(size_t size) function has one parameter, which is the size of memory space to be allocated; Calloc (size_t numelements, size_t sizeoffelement) has two parameters: the number of elements and the size of elements
③ Function return value: malloc() returns the object, and calloc() returns the array
④ Efficiency: malloc() is more efficient than calloc()

3.HASH_FIND

(1) According to different data types of key values, we use different types of interfaces to find the hash structure corresponding to the key value. The common ones are: the search interface provided by Uthash for integer keys is HASH_FIND_INT； The search interface provided for character keys is HASH_FIND_STR……
(2)HASH_ FIND_ Int (hashtable, & key, s): the first parameter hashtable represents the user-defined hash table pointer, the second parameter represents the address of the key value key, and the third s is the output structure pointer variable.
(3) Return value of this function: when the corresponding key value is found in the hash table hashtable, s returns the structure of the given key. When the corresponding key value is not found, it returns NULL.

4.HASH_ADD

(1) Depending on the data type of the added key value, we use different types of interfaces. The common ones are: HASH_ADD_INT indicates that the added key value is of type int, HASH_ADD_STR indicates that the added key value is of character type, HASH_ADD_PTR indicates that the added key value is of pointer type, HASH_ADD indicates that the added key value can be of any type.
(2)HASH_ADD_INT(hashtable, key, s): the first parameter hashtable represents the user-defined hash table pointer, the second parameter represents the name of the key, and the third s refers to the structure pointer variable to be added.

5. Understand the algorithm idea of whether to find the corresponding element in the hash table in the two number addition function

If (it! = null) / / if found
{
int* ret = malloc(sizeof(int) * 2);// Apply for space for ret
//ret[0] is the element subscript corresponding to target num [i], and ret[1] is the element subscript corresponding to num [i]
ret[0] = it->val, ret[1] = i;
*returnSize = 2;// Set the length of the returned array to 2
return ret;// Returns the subscript of two elements
}
insert(nums[i], i);// If not found, insert num [i] into the hash table

If the node corresponding to target num [i] is found in the hash table, the value and I of target num [i] are returned. Otherwise, Num [i] is added to the hash table, which can effectively avoid repeated traversal to the same element.

4, Summary

After analyzing and summarizing the problem of "adding two numbers", I have a deeper understanding of hash table. In the future, I will also add a solution to this kind of key value pair problem - hash table. Although violent solution is also a method, the road of learning can not stand still, We need to seek different solutions to a problem to expand our knowledge and try to solve more than one problem.
This is my first article published on CSDN, and also witnessed my fledgling trip to leetcode. I hope the friends who see this article can grow up with me!!! Let's cheer together!

Reference link 1: Use of C language hash table.
Reference link 2: Usage of Uthash.