Leedcode 1 - sum of two numbers

https://leetcode-cn.com/problems/two-sum/

One 、 subject

Given a An array of integers nums And a Integer target target, Please enter your name in the array find And is the target value target the Two integers , and return Their The array subscript .
You can Suppose that each input corresponds to only one answer . however , The same element in the array cannot be repeated in the answer .
You can return the answers in any order .

Two 、 Function description

**/** *  Parameters ： * nums： Enter the first address of the array （ Input ） * numsSize： Enter the array length （ Input ） * target： Sum of two integers （ Input ） * returnSize： Return data length （ Output ） *  Return value ： preservation  nums  Array  2  The sum of the values equals  target  Data  2  An array of subscripts  */
/** * Note: The returned array must be malloced, assume caller calls free(). */
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    
    
}**

3、 ... and 、 Example

Example 1 ：

 Input ：nums = [2,7,11,15], target = 9
 Output ：[0,1]
 explain ： because  nums[0] + nums[1] == 9 , return  [0, 1] .

Example 2 ：

 Input ：nums = [3,2,4], target = 6
 Output ：[1,2]

Example 3 ：

 Input ：nums = [3,3], target = 6
 Output ：[0,1]

Four 、 Advanced

You can come up with a time complexity less than O(n*n) The algorithm of ？

5、 ... and 、 Write answers

1、 Ideas

Index from the array 0 Start , To numsSize -1 Enumerate data . For each nums[i] lookup target - x Whether there is .

2、 Code

/** * Note: The returned array must be malloced, assume caller calls free(). */
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    
    int *result = NULL;
    int i = 0,j=0;
    for(i=0;i<numsSize-1;i++){
    
        for(j=i+1;j<numsSize;j++){
    
            if(nums[i]+nums[j] == target){
    
                result = (int*)malloc(sizeof(int)*2);
                result[0] = i,result[1] = j;
                *returnSize = 2;
                return result;
            }
        }
    }
    *returnSize = 0;
    return result;
}

3、 analysis

Time complexity ：O(N*N), among N Is in the array Element quantity . The worst Any two numbers in the next array must be matched once .
Spatial complexity ：O(1).

5、 ... and 、 All solutions

1、 The first one is ： Violence enumeration

Their thinking ： The easiest way to think of it is enumeration Every number in the array x, seek Whether there is... In the array target - x. Enumerating data There will be a cycle （ Time complexity O(N)）, lookup target - x A loop will be nested （ Time complexity O(N)）, So the total time complexity is O(N*N).

2、 The second kind ： Hashtable

Their thinking ： adopt Hashtable Complete the data enumeration , Proceed again seek target - x Whether there is . Use Hashtable , You can look for target - x The time complexity is reduced to from O(N) Down to O(1), lookup target - x A loop will be nested （ Time complexity O(N)）, So the total time complexity is O(N).

6、 ... and 、 Additional explanation

1、 Hashtable

https://cloud.tencent.com/developer/article/1781904
https://blog.csdn.net/weixin_34153142/article/details/104867504
https://blog.csdn.net/qq_39630587/article/details/77196367
https://zhuanlan.zhihu.com/p/144296454

2、 Prime number （ prime number ）

https://baike.baidu.com/item/%E8%B4%A8%E6%95%B0/263515