1. sum of two numbers (leetcode topic)

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 .

Their thinking

Train of thought ： Violent solution .
Judge the sum of every two elements in the array in turn target The size of the relationship , You can get the subscript of two equal elements , And back to .
Time complexity ：O(N^2)
Spatial complexity ：O(l)

Train of thought two ： Hashtable .
Use the particularity of hash table to judge , lookup hash Whether the table has and target-nums[i] Equal elements , Add data every time hash In the table .
Time complexity ：O(n)
Spatial complexity ：O(n)
notes ： 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 .

Code

Solution 1 ： Violent solution

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

Solution 2 ： Hashtable .

    public static int[] twoSum_hash(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];
            }

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/two-sum