The first question of leetcode -- sum of two numbers

Sum of two numbers

One more fight today 、 More laughter tomorrow

Sum of two numbers
https://leetcode.cn/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-solution/

1. Title Description ：

Given an array of integers nums And an integer target value target, Please find... In the array And is the target value target the Two Integers , And return their array subscripts .
You can assume 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 .
source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/two-sum

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]

Tips ：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
There will only be one valid answer
Advanced ： You can come up with a time complexity less than O(n2) The algorithm of ？

2. Their thinking ：

2.1 Method 1 ： Violence enumeration

2.1.1 Ideas and algorithms

The easiest way to think of is to enumerate the sum of two numbers in an array equal to target.
Each element cannot be used twice , So we just need to x Look for... In the following elements target - x.

2.1.2 Code

public static int[] twoSum(int[] nums, int target) {
    
    for (int i = 0; i < nums.length - 1; i++) {
    
        for (int j = i + 1; j < nums.length; j++) {
    
            if (nums[i] + nums[j] == target) {
    
                return new int[]{
    i, j};
            }
        }
    }
    return null;
}

2.1.3 Complexity analysis

• Time complexity ：O(N²), among N Is the number of elements in the array . In the worst case, any two numbers in the array must be matched once .
• Spatial complexity ：O(1).

2.2 Method 2 ： Hashtable

2.2.1 Ideas and algorithms

Note that the reason for the high time complexity of method 1 is to find target - x The time complexity of is too high . therefore , We need a better approach , Can quickly find whether the target element exists in the array . If there is , We need to find out its index .

Use hash table , You can look for target - x The time complexity is reduced to from O(N)O(N) Down to O(1)O(1).

So we create a hash table , For each of these x, We first query the hash table for the presence of target - x, And then x Insert into hash table , You can guarantee that you won't let x Match yourself .

2.2.2 Code

public int[] twoSum(int[] nums, int target) {
    
            Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>(nums.length-1); //HashMap It is recommended that we specify the initialization capacity as much as possible during initialization , Reduce the number of expansion 
     //HashMap< The value of the array , The corresponding array subscript >
    for (int i = 0; i < nums.length; ++i) {
    
        if (hashtable.containsKey(target - nums[i])) {
     // In the hash table key Does it include target-nums[i]
            return new int[]{
    hashtable.get(target - nums[i]), i};
        }
        hashtable.put(nums[i], i);
    }
    return new int[0];
}

2.2.3 Complexity analysis

• Time complexity ：O(N), among N Is the number of elements in the array . For each element x, We can O(1) Looking for target - x.

• Spatial complexity ：O(N), among N Is the number of elements in the array . Mainly for the cost of hash table .

3. Look up table method

• While traversing , Record some information , To eliminate a layer of circulation , This is a “ Space for time " Ideas
• You need to record the traversed value and its corresponding subscript , It can be realized with the help of lookup table
• There are two common implementations of lookup tables :
• Hashtable
• Balanced binary search trees