Leetcode-1. Sum of two numbers (Application of hash table)

Preface :
stay Leetcode First simple question - The sum of two numbers algorithm problem , I directly took violence to solve two levels for Cycle to solve the problem , Next, I'm in the discussion area , See a new solution , Take advantage of Map Containers , And in further understanding Map Container found , original Map Containers -hash_map The bottom of the set is the hash table , Hash table , This enables us to learn hash tables with java Medium hasMap Gather and associate to understand .

Let's look at the original question :

Given an array of integers nums And an integer target value target, Please find... In the array And is the target value the Two Integers , And return their array subscripts . You can assume that each input corresponds to only one answer . however , The same element in an array cannot be used twice .
You can return the answers in any order .
source ： Power button （LeetCode）

First of all, mine

Violence solution :

The idea is easy to understand , It is through for The loop first determines a number , And then again for Whether the number after loop traversal is equal to the difference between its target value and the determined number .

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

 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 once .
Spatial complexity ：O(1).

then , In the discussion area , It was proposed , Its comparison obviously has many repetitive results , In order to make every time for Cycles are more meaningful . We store the compared value and the corresponding subscript into hasMap Collection , And in the hasMap The efficiency of searching in the set is very high . Therefore, it introduces Map Concept of container .
about Map If the container has something you don't understand , Take a look at this article : Map Interpretation of container

Hash solution

It mainly uses hasMap aggregate , stay hasMap The query time complexity in the set is constant , Although it consumes a lot of memory space , But it has a good performance in terms of time efficiency .

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

 Complexity analysis 

Time complexity ：O(N), among N Is the number of elements in the array . because hasMap The query time complexity in the set is constant , 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 .