As a rookie programmer, it can be said that, from a large number of CRUD business, developed a copy and paste can be used.

Because we don’t all say: program = copy + Baidu, and then a bit more advanced is copy + Google. (I can’t help but think, is science ^ Internet advanced?)

Anyway, the code can run, it is done, if not, delete library run is also very easy.

However, due to the topic of “35-year-old programmer crisis” constantly flowing out on the Internet, I have to start thinking seriously about how far I am from turning 35 as a young man approaching 30.

Plus, all my friends are talking about the importance of algorithms, so I really need to rethink the definition of “program.” Check out the official definition of the serious version below…

Program = algorithm + data structure

As a result, I began to appreciate the importance of algorithms and data structures. Those lie in net dish collect edition, also be time to take out bask in.

But, see a theory only, do not do a problem, that is not play rascal. At least I am also a decent, upright good youth, can not live up to force buckle (LeetCode) for the majority of age-appropriate programmers.

Great oaks from little acorns grow. I had to get an account first. But I forgot all about it). How brush title method, again make difficult, fortunately I have Baidu, Google (cough cough, said good need not search engine).

At this time, found out in some on to see a particularly interesting words, saying that there are brothers from the “sum of two numbers” to start the algorithm road, from then on the uncontrollable change. When the general manager, as CEO, married a rich woman oh not baifumei, onto the peak of life.

Oh, my god, it’s so amazing. I don’t believe it, I also saw that special bright four big words “the sum of two numbers” on the home page, how a little click desire are not it.

In order to feel the change for myself, I decided to check it out. This does not look unimportant, after a look, I also become out of control, I actually faint feeling, yhoo, this problem is quite interesting? !

The original question is as follows:

Given an array of integers nums and a target value target, find the two integers in the array and the target values and return their array subscripts. You can assume that there is only one answer for each type of input. However, you cannot reuse the same elements in this array. Example: Given nums = [2, 7, 11, 15], target = 9Copy the code

And a lot of people are going to say, “Wow, bam, bam, two for loops.” Let’s see what I can do. (I set target to 13)

public class SumTest { public static void main(String[] args) { int[] arr = {2, 7, 11, 15}; int[] result = sumTwo(arr , 13); System.out.println(Arrays.toString(result)); } private static int[] sumTwo(int[] nums, int target) { for (int i = 0; i < nums.length - 1; i++) { for (int j = i + 1; j < nums.length; j++) { if(nums[i] + nums[j] == target){ return new int[]{i,j}; } } } return null; }}Copy the code

The idea is that the outer loop starts at the first element in the array, and we call the loop variable I, so the inner loop j starts at I +1. Finally, if the sum of the two elements is equal to the target value, you get the corresponding array index.

That’s true, but it doesn’t take time into account. We know that the superposition of the two loops will increase the time complexity to O (n ^ 2), which is not obvious for small data volumes, and the execution efficiency will plummet (oh, no, it will plummet square) for large data volumes.

I really can’t think of any good ideas. Fortunately, there are discussion area, and solution area, you can watch the various gods to solve the problem ideas, as well as the official solution.

Sure enough, I found an even better algorithm. And see,

private static int[] sumTwo(int[] nums, int target) {

    HashMap<Integer, Integer> map = new HashMap<>();

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

        map.put(nums[i],i);
    }
    return null;
}Copy the code

The above time complexity goes directly to O (n). What’s the idea? It’s just using a hash table, matching the elements in the array with their subscripts as kv pairs. As we loop, we put them in turn into the hashMap. Then check whether there is a key such as “target value minus current key value” in the map, return if there is.

For example, if I save a key in the map that is “2”, then I only need to find a key that is (13-2 = 11), which means that their sum is 13. These are the two numbers I’m looking for, so just return their subscripts.

This idea is really very magical, I exclaim in the heart, is really SAO operation, only you can not think of, no god can not do.

Let’s take a look at how the program steps work in this way. (Take and as 13 for example)

Array: [2, 7, 11, 15], target = 13 step1: key = 2, value = 0, 13-2 = 11 Step3: key = 11, value = 2, 13-11 = 2, it can be found that 2 already exists in the map. Therefore, we return the indices 0 of 2 and 2 of 11.Copy the code

Isn’t that amazing? First of all, this code looks much bigger than the double-layer loop above. And the second thing is that the time goes from O (n^2) to O (n).

It’s like I’ve opened a magical door to the algorithm (don’t laugh at me, squirt). So, by the way, the daily 1 question also gave to do, get 10 points, elated.

The first day, I hope I can stick to it!

It’s easy to start something, but it’s hard to stick to it. Stick to it, you will surpass a lot of people, mutual encouragement!

If this article is useful to you, please like it, comment on it, and retweet it.

Learning is boring and interesting. I am “Misty rain sky”, welcome to pay attention to, can be the first time to receive the article push.