1. Sum of two numbers (hash table)

  subject ：

Given an array of integers nums  And a target value target, Please find and as the target value in the array   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 .

Example :

Given nums = [2, 7, 11, 15], target = 9

because nums[0] + nums[1] = 2 + 7 = 9

So back [0, 1]

Method ： Hash table method

Ideas ： Hash table is a method of exchanging space for time , If violent solutions are used , Then the time complexity is O(n^2), If the complexity of the hash table is reduced to time O（n）, One traversal completes the task

import java.util.HashMap;
import java.util.Map;

public class Liangshuxiangjia {
    public int[] twoSum(int [] nums,int target){
        int [] res = new int[2];
        // If the array is empty , Return an empty array 
        if(nums == null || nums.length ==0){
            return res;
        }
        // New hash table 
        Map<Integer,Integer> map  = new HashMap<>();
        // Traversal array , Judge map Whether there is a value equal to target-num[i]
        // If there is , Returns the value of the current element , as well as target-num[i]
        //  without , take target-nums[i] The difference is stored in the set 

        for (int i = 0; i <nums.length; i++) {
            int temp = target-nums[i];
            if(map.containsKey(temp)){
                res[1] = i;
                res[0] = map.get(temp);
            }
            map.put(nums[i],i);
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {2,5,6,7};
        Liangshuxiangjia liangshuxiangjia = new Liangshuxiangjia();
        int [] res = liangshuxiangjia.twoSum(nums,9);
        for (int x:res) {
            System.out.print(x+" ");
        }
    }
}

Output results ：

0 3

Time complexity ：O(n)