The introduction

Some time ago, I saw an article about LeetCode, which made me deeply touched. When I was in college, I did not study algorithms much, so I am not good at algorithms until now.

There has always wanted to fill their own this short board, in fact, has been to find reasons for their excuses.

As a result, I ate too much tonight, so I made up my mind to brush a wave of LeetCode questions. During the process, I wrote some articles to share with you (in fact, it has a good urging effect).

I will not introduce more about the background of LeetCode. I plan to brush only the easy and medium difficulty problems. It is said that these two difficulties are basically enough, and as for the difficulty, I will wait until I finish the first two parts.

Roughly talk about the brush problem routine, first look at the topic, 5 minutes or so without train of thought directly look at the answer, this thing without train of thought is really no way, there is no basic reserve to do the problem is still a little difficult.

After reading the answers, it is very important to write the code by yourself. Now we are interviewing a lot of whiteboard code, be sure to write it by yourself, writing will effectively deepen memory.

This series of articles planned for the day, originally thought it was not a difficult thing, but when I saw this:

There were more than 1700 questions, and even after removing the difficult parts, there were still more than 1000 questions in 2/3 of them. I really made a great start for myself, and I made a plan for the next two or three years.

Students who are interested in my plan can punch in the message area with me every day. It is expected that each article will take about 3 minutes to read, and the total time for writing and debugging codes will not exceed half an hour. The code used is Java, which would be a bit tricky to write in Python.

To do things, it is important to stick to them.

If you need code, you can visit my GitHub and Gitee to get it. I will submit the code to these two code repositories synchronously every day:

GitHub:github.com/meteor1993/…

Gitee:gitee.com/inwsy/LeetC…

Title: Sum of two numbers

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, the same element in an array cannot be used twice.

Example:

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

Train of thought

First to sort out the train of thought, although the topic goal is to require an addition, use the program directly write addition a bit is not so good, a little change, using the target array target minus nums in a value, if the result is also in the array, then we will complete to solve problems.

Violent solution

My first thought is also the simplest plan, is the violence plan, directly two cycles set, violence to calculate, get the result:

public int[] twoSum_1(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        int temp = target - nums[i];
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] == temp) {
                return new int[]{i, j}; }}}throw new IllegalArgumentException("No two sum solution");
}
Copy the code

The disadvantage of this scheme is a little high time complexity, the advantage is simple, should be everyone can think of the scheme.

Because there are n elements, and for each of those elements, we have to walk through the array to see if there is an element that we need, which takes order n time.

Time complexity: 。

Space complexity: O(1).

Double hash table

So the idea of optimizing the violence scenario is that we need to iterate through the entire array at least once, and the point is that in that iteration, we’re going to look for a way that we can go faster and more efficiently than we can go through one layer of loops to find the values that we want in the entire array.

We can do this with the help of a hash table, which enables fast lookups with “approximately” constant time.

public int[] twoSum_2(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], i);
    }
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if(map.containsKey(complement) && map.get(complement) ! = i) {return new int[] {i, map.get(complement)}; }}throw new IllegalArgumentException("No two sum solution");
}
Copy the code

We iterate over the list of n elements twice. Because the hash table reduces the lookup time to O(1), the time complexity is O(n).

Time complexity: O(n).

Space complexity: O(n).

One-time hash table:

So what we did is we put the array in the hash table, and then we iterate through it, and we can actually iterate through it until at some point, we hit our target, and then we can just return the data, and then we don’t have to put any more data in the hash table.

public int[] twoSum_3(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}
Copy the code

Although this approach looks more efficient than the previous two hashes, in fact the time and space complexity is the same, also:

Time complexity: O(n).

Space complexity: O(n).