Force is brushed buckle problem for the sum of two Numbers

The Sum of Two Numbers

This question is the first question of Likou, and it is the place where the dream of brushing questions begins.It must not be underestimated, because I am very disheveled.

The title is as follows:

Given an integer array nums and an integer target value target, please find the two integers in the array that are the target value target and return their array indices.You can assume that there will only be one answer for each input.However, the same element in the array cannot be repeated in the answer.You can return answers in any order.

The requirements of the title are given an array, given a target value, and then let you find the sum of two values ​​in the array equal to the target value, and then return their subscripts.

Normally we don't find the target data so quickly.There is usually a traversal process.A move index is added to the following value.Similar to this.Know to find the target value.

Such code is implemented like this.

for (int i = 0; i < nums.length; i++) {for (int i1=i+1; i1 < nums.length; i1++) {if(nums[i]+nums[i1]==target){arr[0]= i;arr[1]=i1;}}}

Copy

According to this logic, we still use a double for loop. When looking for the target value, we will traverse to the elements that have been traversed before, which is repetition.

For example, 2+7 2+11 2+15 ··· Then we still go through 11, 15 when adding 7 and the following numbers.In this way, with the traversal of the number of searches and the increase in the amount of data, it is inevitably a waste of time and efficiency.

So we try to solve the problem in this way. After we can traverse this element again, we will write it down, and then we will not use it directly next time, which is great.And can correspond to values ​​and subscripts.Now here is the initialization, the arrow is the traversal index move.

At the beginning, we start with 4. The difference between 4 and the target value is 16. There must be no hashmap, so we put 4 and its index into it.

Then continue, when we get here, we go to 7 to find 13, and find that there is just this key in the map, so we just return the vaue corresponding to this key, and the value is the index.Of course, you can do it the other way around.

Think about it, if we still use brute force exhaustion, then is it still a for loop when we reach 7, then it is 4+6 4+7 … 4+13 …

6+13 6+8 … 13+8 13+7 In this way, we have repeated the traversal value. From this small amount of calculation, we can find that we have used 13 5 times in total, and if we use hashmap,We just pass it once, record it, and then we can find it directly later.Is it very convenient.Implementation code

 HashMap map = new HashMap<>();for (int i = 0; i < nums.length; i++) {int result = target-nums[i];if(map.containsKey(result)){map.get(result);arr[1]=i;arr[0]=map.get(result);}else {map.put(nums[i],i);}}

Copy

This efficiency is very high.

Simpleness is one thing, but it is another matter whether the simple questions can be well understood.Simple questions do not have a higher pass rate than difficult questions.

Sometimes the understanding of knowledge is temporarily understood. If the algorithm foundation is not solid, it will be forgotten immediately, and then it will fall into doubt again.Algorithms are based on data structures plus basic grammar knowledge.