The sum of two digits of a small algorithm per day

Given an array of integers nums and a target value, you can find the two integers that sum to the target value in the array and return their array subscripts.

You can assume that each input corresponds to only one answer. However, you can't reuse the same elements in this array.

Example:

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

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

So go back [0, 1].

Is this topic very simple?

This article is from Kay Java(kaigejava).

First, the first solution we came up with was the for loop. Nested loops. As follows:

JAVA code:

public static void main(String[] args) {
    Integer [] nums  = new Integer []{1,2,0,5,7,9,3};
    Integer target  = 5;
    Integer[] returnNums  = twoSum(nums,target);
    System.out.println(JSON.toJSONString(returnNums));
}
public static Integer[] twoSum(Integer[] nums, Integer target) {
    Integer[] returnNums = new Integer[2];
    for (int i = 0; i < nums.length; i++) {
        for (int j = i+1; j < nums.length; j++) {
            int num1 = nums[i];
            int num2 = nums[j];
            if ((num1 + num2) == target) {
                returnNums[0] = i;
                returnNums[1] = j;
                return returnNums;
            }
        }
    }
    return returnNums;
}

Operation results:

The result of execution is out. Let's look at the execution time:

Is it a low way?

Next, let's look at the second algorithm:

The second algorithm is ingenious. The Java code is as follows:

private  Integer[] twoSum2(Integer[] nums, Integer target) {
    Integer[] indexs = new Integer[2];
    //Establish k-v, one-to-one hash table
    HashMap<Integer,Integer> hash = new HashMap<Integer,Integer>();
    for(int i = 0; i < nums.length; i++){
        if(hash.containsKey(nums[i])){
            indexs[0] = i;
            indexs[1] = hash.get(nums[i]);

            log.info(JSON.toJSONString(hash));
            return indexs;
        }
        //Store data in key as complement and value as subscript
        hash.put(target-nums[i],i);
        log.info("==>:{},i=:{},target-nums[i]:{}",nums[i],i,target-nums[i]);
    }
    return indexs;
}

The clever points are:

Look again at the results of the operation:

Look at the comparison of the two algorithms:

Is it much faster than that?

Welcome to leave a better algorithm. Study together and grow together