This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

💨 1. Preface

  • Hello, everyone, I am xiao Cheng, finally, I will “talons” extended to the algorithm, before writing “algorithm diary”, I also considered many questions, now on the Internet about the Leetcode algorithm so many cases, I again “make wheels” is not necessary.

  • Last chatted and circle of friends, be able to chat friends or good), but the worry is redundant, in the process of writing, I have made a progress, not only in the algorithm and the writing may also help some “reason” to see the friends of the article, so even if the repeated “rolling” and how.

  • “Algorithm Diary” series features: pay more attention to the combination of the actual situation, the algorithm and the actual development of questions or interview examples combined, so that the learning algorithm is more meaningful. (Read on!)

  • If the article is helpful to you, you can help to subscribe to the three key and column oh!

🔮 two, two numbers sum

🔴 2.1 algorithm topic

Given an integer array nums and an integer target value target, find the integer in the array and the target value target and return their array subscripts.

You can assume that there is only one answer for each type of input. However, the same element in the array cannot be repeated in the answer. Return answers in any order.

Example:

Example 1: Enter nums = [2.7.11.15], target = 9Output:0.1Because nums[0] + nums[1] = =9To return to the [0.1]. Example 2: Enter nums = [3.2.4], target = 6Output:1.2] Example 3: Enter nums = [3.3], target = 6Output:0.1]
Copy the code

🟠 2.2. Analyze the topic

Enter a target value, find two elements in the array and return their subscripts. The same element in the array cannot be repeated in the answer.

The result must be [0,1] or [1,0], not [0,0] or [1,1], that is, it cannot return the same index.

🟡 2.3. Solution 1

1. How to solve the problem

Use the for loop + if condition to find two elements consistent with the target value. Here’s how to do it:

    /** * Double for loop *@param nums
     * @param target
     * @return* /
    public static int[] twoSum2(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = 1; j < nums.length; j++) {
            	// Compare the query to find two elements that match the target values
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j}; }}}return null;
    }
Copy the code


Ii. Review of problem solving schemes

If you solve this problem in an interview, the interviewer will give you a maximum of 60 points. Why? We need to see what the time complexity of this algorithm is! (If you don’t know the time complexity and algorithm metrics, please read my last article first.

From the article on algorithm knowledge, we can know that the time complexity is mainly proportional to the number of times the basic operations are performed that consume the running time. Looking further at the program above, we see that the basic operation on the elapsed time is actually the statement for the if condition.

With the increase of problem size n, its number of judgments will also increase. In the expression of problem size function, f(n) = N2n ^2n2, even if its time complexity is O(n2n^2n2), is there a better way to optimize it? The answer is yes, keep reading!

🟢 2.4. Optimization of solution 1

First, optimization ideas

The above plan “brute force” approach, we use the worst situation is two loops to the last element was able to find answers to conform to the topic, now that we know that the run time is spent on the comparison of the if condition logic, whether can be reduced by decreasing the comparison logic operation time, that’s right, do exist can be optimized, the method of Let’s take a look at the optimized code.

Second, the optimized code

/** ** ** ** ** ** ** ** ** ** ** *@param nums
     * @param target
     * @return* /
    public static int[] twoSum2(int[] nums, int target) {
        // The purpose of length-1 is to select a maximum/minimum value by comparing it with other elements of the set in each round
        // means that the last element has already been compared to all the previous elements without needing to loop again
        for (int i = 0; i < nums.length - 1; i++) {
            // j = I + 1: the comparison element skips the comparison with itself
            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


For (int j = I + 1; int j = I + 1; j < nums.length; In j++), the main meaning of this is: each round will filter out the outermost element that has been compared before, and no repeat comparison will be carried out, which can be clearly understood through the following case.

For example, to loop through an array [1, 2, 11, 7] to find two elements with subscripts and 9, we would do the following:

1. In the first round of the loop, the outer layer will use [1] and the inner layer [2, 11, 7] to do operations, but there are no two elements that meet the conditions, and the loop continues.

2. In the second outer cycle, take 2 and [11,7] in the inner layer as elements, and get the results that meet the conditions. If not, the third and fourth rounds will be continued by analogy… In the operation.

By this operation, we will find that each loop will skip has compared before elements (because has confirmed that they are not meet the conditions), namely the inner loop is started with the I + 1, this reduces unnecessary comparison, saving operation time, let’s push it to the next time complexity.

3. Derive the time complexity of the optimized code

The number of inner loops (j

Through the summation of arithmetic sequence: Sn= Na1 +n(n-1) D /2, we can get the time-consuming function F (n) = Na1 +n(n-1) D /2. According to the inference of big O notation, we can get the time complexity of the optimized method is O(N2n ^2n2). If you don’t know big O, look at my last article.

Fourth, what is the significance of this optimization method

The time complexity calculated by the algorithm after the above optimized scheme is still O(n2n^2n2). There must be some questions from students. Since the final time complexity is the same as before the optimization, what is the role of this scheme? Of course, this method is not as efficient as it would be if the input size was infinitely larger, but in the interview, if you can explain it to the interviewer, the interviewer will give you 10 points out of 60. Why?

These 10 points show that you are willing to dig into problems and find ways to improve efficiency. The interviewer is not only looking at your current ability, but also looking at your ability to learn and grow.

🔵 2.5. Solution 2

Since the above optimizations didn’t solve our problem, we needed to take a different approach. I believe that students have more or less heard of the two concepts of “using time for space and using space for time”, so can we adopt this method in this topic? Yes, the solution to this problem is to exchange space for time. Here’s how to do it.

    public static int[] twoSum(int[] nums, int target) {
    	// Use HashTable to store array values and subscripts
        Hashtable<Integer, Integer> keyMap = new Hashtable<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
        	// Each loop determines if there are values in the hashTable that add to the value of the current loop equal target, and returns if there are
            if (keyMap.containsKey(target - nums[i])) {
                return new int[]{keyMap.get(target - nums[i]), i};
            }
            // If no value is found, store the element value and subscript
            keyMap.put(nums[i], i);
        }
        return null;
    }
Copy the code


From the above code, you can find that the problem size function f(n) = n(that is, there is only one layer of loop, and the number of cycles increases with the increase of n), and the time complexity can be concluded as O(n) through the big O notation. The above algorithm introduces Hashtable, which is to store the values in the array and reduce the inner layer of loop. So this is a way of changing space for time, and let’s see how different O(n) is from O(n2n^2n2) by looking at a concrete picture.

🟣 2.6 Application in actual business

In business, it is very common to use multiple layers of FOR to search for qualified data. For example, to sort some data, we will use selection sorting method, bubble sorting method and so on, which solve sorting problems through FOR.

The time-for-control scheme is also very common in development. For example, in order to improve the speed of data retrieval, we will create corresponding indexes for appropriate fields, so as to quickly locate the needed data. There are also various NoSQL databases, such as Redis, which are essentially time-for-control to improve efficiency.

📑 3. Write at the end

Through three different solutions to above, you will find, to find the best way for most people is a gradual process, a lot of people at first will not immediately think of the use of space for the solution to the problem of time, just like when you started learning algorithm, may also find it difficult, and programming, may also involve mathematical knowledge.

You can have the heart of retreat, but more to have the courage to try, the algorithm looks very difficult, but you can start the first step, try to understand the knowledge of the algorithm, try to solve simple algorithm problems, step by step, you will find that the algorithm is not so difficult, mathematics is not so difficult.

Please remember that! One person can go fast, but a group of people can go farther! Welcome to join the circle of technical people [IT Learning Diary], share resources and grow together!