Hash - 1. Sum of two numbers - some people fall in love during the day, some people watch the sea at night, and some people can't do the first question

1 Title Description

1. Sum of two numbers

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 .

2 Title 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]

3 Topic tips

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• There will only be one valid answer

4 Ideas

Method 1 : Ideas and algorithms of violence enumeration
The easiest way to think of is to enumerate every number in an array x, Look for the existence of target - X.
When we look for target - x when , It needs to be noted that each is located in x All the previous elements have been associated with x Matched , So there's no need to match again . And each element cannot be used twice , So we just need to x Look for... In the following elements target - X .

Complexity analysis
Time complexity :O(N 2), among N Is the number of elements in the array . In the worst case, any two numbers in the array must be matched ─ Time .
Spatial complexity :O(1).

Method 2 : Hash table idea and algorithm
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) Down to 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 .

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 .

5 My answer

Method 1 : Ideas and algorithms of violence enumeration

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

Method 2 ： Hashtable

class Solution {
    
    public int[] twoSum(int[] nums, int target) {
    
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
    
            if (hashtable.containsKey(target - nums[i])) {
    
                return new int[]{
    hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
        return new int[0];
    }
}