Shulou(Shulou.com)06/03 Report--

This article introduces the relevant knowledge of "how to achieve the classic summation problem". In the operation of actual cases, many people will encounter such a dilemma. Next, let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

The sum of two numbers

Topic description:

Given an array of integers nums and a target value target, please find the two integers in the array that are the target values and return their array subscript.

You can assume that each input corresponds to only one answer. However, the same element in an array cannot be used twice.

Example:

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

Return [0,1] because nums [0] + nums [1] = 2 + 7 = 9

The title is easy to understand, that is, to check whether there is a sum of two numbers in the array as the target number, and if so, return two subscript, here to provide you with two solutions double-pointer (violence) method, and hash table method, you can take a look.

Hash table method

Analysis

The hash table is easy to understand, we only need to go through a loop, if our target value is 9 and the current pointer points to a value of 2, we just need to look in the hash table to see if it contains 7, because 9-2 = 7. If it contains 7, we can return it directly, if not, put the current 2 in the hash table, and move the pointer to point to the next element. Note: key is the element value and value is the element index.

Moving picture analysis:

Is it easy to understand? let's take a look at the title code.

Title code:

Double pointer (violence) method

Analysis

The idea of the double pointer method is simple. The L pointer is used to point to the first value, and the R pointer is used to find out from the back of the L pointer whether the array contains a number with the sum of the L pointer pointing to the value as the target value. See the picture below

Example: the green pointer points to a value of 3, and the blue pointer needs to traverse behind the green pointer to find out if it contains the element of target-3, that is, 5-3 = 2, if it contains a return.

Title code

The sum of three numbers

Topic description:

Give you an array of n integers, nums, and determine if there are three elements in nums, such as a + b + c = 0. Please find all the triples that meet the conditions and do not repeat.

Note: duplicate triples cannot be included in the answer.

Example:

Given array nums = [- 1,0,1,2,-1,-4]

The set of triples that meet the requirements is: [[- 1,0,1], [- 1,1,2]]

This topic is an upgrade to the title just now. Just now we only need to return an example, but this topic allows us to return all the situations. On this topic, we need to return all the cases in which the three numbers add up to zero. But we need to remove the repeated triple (which is the core of the question), so this topic is still very interesting. Remember to sign in.

Hash table method

Analysis

The hash table solution of our topic is easy to understand. We first sort the array, and then we store the sorted elements in the hash table, and then we first determine the first two numbers through two layers of traversing. Then we only need whether the hash table has a third number that matches the situation, which is similar to the idea of the violent solution, which is easy to understand, but here we need to pay attention to the situation. For example, our example is [- 2, 1, 1]. If we completely follow the above ideas, there will be two solutions, [- 2, 1, 1] and [1, 1,-2]. The specific reason is that 1 is found in the hash table and stored in the hash table after determining-2pr 1. After determining 1, 1, it is found that-2 is stored in the hash table. So we need to add a constraint to avoid this situation, that is, we only deposit it when the index of our third number is greater than the second number.

In this case, it cannot be saved, because although we have found a value that meets the requirements in the hash table, the index of-2 is 0 less than 2, so it cannot be saved.

Title code

Multiple pointer

Parsing:

If we call the pointer solution of the previous topic double pointers, then the method used in this topic is three pointers, because we are the sum of three numbers, one pointer corresponds to a number, let's take a look at the specific ideas, in fact, the principle is very simple, we first sort the array, directly Arrays.sort () to solve, sorting after processing is very easy. Let's take a look at the initial position of the three pointers.

The initial situation is shown in the picture above, and if we look at the current situation, the sum of the three numbers is-3, which is obviously not zero, so what should we do?

Let's imagine that the sum of our current three numbers is-3 < 0, then if we move the orange pointer, we will make the sum of our three numbers smaller, because our array is orderly, so the sum of the three numbers will become smaller when we move the orange pointer (blue does not move), and if we move the blue pointer (orange does not move), the sum of the three numbers will become larger, so in this case we need to move our blue pointer to the right. Find the case where the sum of the three numbers is equal to 0 and save it. If the sum of the three numbers is greater than 0, you need to move the orange pointer, and save it if the sum of the three numbers is 0. Until the blue and orange pointers meet and jump out of the cycle, and then our green pointer moves one step to the right to continue with the appeal step. But one detail we need to pay attention to here is that we need to remove the same triple. Let's take a look at the example below.

Here we find that 0-1 + 1 = 0, the current situation is consistent, so we need to deposit the triple, after saving, the blue pointer moves backward, the orange pointer moves forward, we find that it is still 0-1 + 1 = 0 is still consistent, but if we continue to deposit in the triple, it does not meet the meaning of the question, so we need to repeat it. HashSet can be used here, but it is too inefficient to recommend. Here we can use the while loop to move the blue pointer to a different position, that is, directly to element 0, and so can the orange pointer. This is the case below, so that we can remove the weight, and then continue to determine whether the sum of the current three numbers is 0.

Moving picture analysis:

Title code:

The sum of four numbers

Topic description

Given an array nums containing n integers and a target value target, it is determined whether there are four elements in nums, such that the values of a + b + c + d are equal to target. Find all quaternions that meet the conditions and do not repeat.

Note:

Duplicate quads cannot be included in the answer.

Example:

Given array nums = [1, 0,-1, 0,-2, 2], and target = 0.

The set of quaternions that meet the requirements are: [- 1,0,0,1], [- 2,0,0,0,2]

We have completed the sum of two numbers and the sum of three numbers, and this problem should be easy to solve, because we already know the framework for solving this kind of problem. then move the pointer to find the second match, the sum of three numbers, fix one number, and double pointers to find the other two digits that match the situation, then the sum of four numbers can also be fixed first. Then use double pointers to find the other two digits. So let's take care of him.

Multiple pointers:

Parsing:

The sum of three numbers is that we first determine a number, and then use double pointers to find the other two numbers. our idea of solving this problem is that we need to first determine two numbers and then use double pointers to find the other two numbers. it is easy to understand that it is basically the same as the sum of three numbers. Our specific ideas can refer to the following figure.

It should be noted here that our target is no longer the same as the sum of three numbers is 0, target is not fixed, so the idea of solving the problem can not completely copy the above problem. In addition, we also need to consider the situation of removing weight here, and the train of thought is consistent with the above topic.

The above figure shows us the situation of a qualified quad. After the search is successful, the next step is to move the blue pointer, redefine the green and blue pointer, and continue with the above steps.

Moving picture analysis:

Title code:

This is the end of the content of "how to achieve the classic summation problem". Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.